共查询到20条相似文献,搜索用时 343 毫秒
1.
2.
研究了单位$l_{\infty}$ 范数下边权有界的最小支撑树逆最优值问题。给定一个边赋权无向连通网络$G=(V, E, w)$ , 支撑树$T^0$ , 下界向量$\bm{l}$ , 上界向量$\bm{u}$ 及数值$K$ , 寻求一个新的边权向量$\bm{\bar{w}}$ 满足上下界约束$\bm{l}\le\bar{\bm w}\le {\bm u}$ , 且$T^0$ 是在向量$\bm{\bar{w}}$ 下权值为$K$ 的一个最小支撑树, 目标是在单位$l_{\infty}$ 范数下使得修改成本$\|\bar{\bm w}-{\bm w}\|$ 最小。本文给出了该问题的数学模型, 分析了其最优性条件, 设计了求解该问题的时间复杂度为$O(|V||E|)$ 的强多项式时间算法。 相似文献
3.
研究了单位$l_{\infty}$ 范数下边权有界的最小支撑树逆最优值问题。给定一个边赋权无向连通网络$G=(V, E, w)$ , 支撑树$T^0$ , 下界向量$\bm{l}$ , 上界向量$\bm{u}$ 及数值$K$ , 寻求一个新的边权向量$\bm{\bar{w}}$ 满足上下界约束$\bm{l}\le\bar{\bm w}\le {\bm u}$ , 且$T^0$ 是在向量$\bm{\bar{w}}$ 下权值为$K$ 的一个最小支撑树, 目标是在单位$l_{\infty}$ 范数下使得修改成本$\|\bar{\bm w}-{\bm w}\|$ 最小。本文给出了该问题的数学模型, 分析了其最优性条件, 设计了求解该问题的时间复杂度为$O(|V||E|)$ 的强多项式时间算法。 相似文献
4.
5.
本文研究工件有到达时间且可拒绝下的同类平行机排序问题。在该问题中, 给定一个待加工工件集, 每个工件在到达之后, 可以被选择安排到$m$ 台同类平行机器中的某一台机器上进行加工, 也可以被选择拒绝加工, 但需支付一定的拒绝惩罚费用。目标函数是最小化接受工件集的最大完工时间与拒绝工件集的总拒绝费用之和。当$m$ 为固定常数时, 设计了一个伪多项式时间动态规划精确算法; 当$m$ 为任意输入时, 设计了一个近似算法, 当接受工件个数大于$(m-1)$ 时, 该算法近似比为3, 当接受工件个数小于$(m-1)$ 时, 该算法近似比为$(2+\rho)$ , 其中$\rho$ 为机器加工速度最大值和最小值的比值。最后通过算例演示了算法的运行。 相似文献
6.
本文研究工件有到达时间且可拒绝下的同类平行机排序问题。在该问题中, 给定一个待加工工件集, 每个工件在到达之后, 可以被选择安排到$m$ 台同类平行机器中的某一台机器上进行加工, 也可以被选择拒绝加工, 但需支付一定的拒绝惩罚费用。目标函数是最小化接受工件集的最大完工时间与拒绝工件集的总拒绝费用之和。当$m$ 为固定常数时, 设计了一个伪多项式时间动态规划精确算法; 当$m$ 为任意输入时, 设计了一个近似算法, 当接受工件个数大于$(m-1)$ 时, 该算法近似比为3, 当接受工件个数小于$(m-1)$ 时, 该算法近似比为$(2+\rho)$ , 其中$\rho$ 为机器加工速度最大值和最小值的比值。最后通过算例演示了算法的运行。 相似文献
7.
8.
9.
10.
11.
非负矩阵分解是一种流行的数据表示方法,已广泛应用于图像处理和模式识别等问题.但是非负矩阵分解忽略了数据的几何结构. 而现有的基于简单图的学习方法只考虑了图像的成对信息,并且对计算相似度时的参数选择非常敏感. 超图学习方法可以有效地解决这些问题. 超图利用超边将多个顶点相连接用以表示图像的高维结构信息. 然而, 现有的大部分超图学习方法都是无判别的学习方法.为了提高识别效果, 提出了基于具有判别信息的超图和非负矩阵分解方法的新模型, 利用交替方向法进行迭代求解新模型, 并结合最近邻方法进行人脸识别. 在几个常用标准人脸图像数据库上进行实验, 实验结果表明提出的方法是有效的. 相似文献
12.
We consider tomographic reconstruction using priors in the form of a dictionary learned from training images. The reconstruction has two stages: first we construct a tensor dictionary prior from our training data, and then we pose the reconstruction problem in terms of recovering the expansion coefficients in that dictionary. Our approach differs from past approaches in that (a) we use a third-order tensor representation for our images and (b) we recast the reconstruction problem using the tensor formulation. The dictionary learning problem is presented as a non-negative tensor factorization problem with sparsity constraints. The reconstruction problem is formulated in a convex optimization framework by looking for a solution with a sparse representation in the tensor dictionary. Numerical results show that our tensor formulation leads to very sparse representations of both the training images and the reconstructions due to the ability of representing repeated features compactly in the dictionary. 相似文献
13.
Structure-enforced matrix factorization (SeMF) represents a large class of mathematical models appearing in various forms of principal component analysis, sparse coding, dictionary learning and other machine learning techniques useful in many applications including neuroscience and signal processing. In this paper, we present a unified algorithm framework, based on the classic alternating direction method of multipliers (ADMM), for solving a wide range of SeMF problems whose constraint sets permit low-complexity projections. We propose a strategy to adaptively adjust the penalty parameters which is the key to achieving good performance for ADMM. We conduct extensive numerical experiments to compare the proposed algorithm with a number of state-of-the-art special-purpose algorithms on test problems including dictionary learning for sparse representation and sparse nonnegative matrix factorization. Results show that our unified SeMF algorithm can solve different types of factorization problems as reliably and as efficiently as special-purpose algorithms. In particular, our SeMF algorithm provides the ability to explicitly enforce various combinatorial sparsity patterns that, to our knowledge, has not been considered in existing approaches. 相似文献
14.
The Alternating Nonnegative Least Squares (ANLS) method is commonly used for solving nonnegative tensor factorization problems. In this paper, we focus on algorithmic improvement of this method. We present a Proximal ANLS (PANLS) algorithm to enforce convergence. To speed up the PANLS method, we propose to combine it with a periodic enhanced line search strategy. The resulting algorithm, PANLS/PELS, converges to a critical point of the nonnegative tensor factorization problem under mild conditions. We also provide some numerical results comparing the ANLS and PANLS/PELS methods. 相似文献
15.
Operations with tensors, or multiway arrays, have become increasingly prevalent in recent years. Traditionally, tensors are represented or decomposed as a sum of rank-1 outer products using either the CANDECOMP/PARAFAC (CP) or the Tucker models, or some variation thereof. Such decompositions are motivated by specific applications where the goal is to find an approximate such representation for a given multiway array. The specifics of the approximate representation (such as how many terms to use in the sum, orthogonality constraints, etc.) depend on the application.In this paper, we explore an alternate representation of tensors which shows promise with respect to the tensor approximation problem. Reminiscent of matrix factorizations, we present a new factorization of a tensor as a product of tensors. To derive the new factorization, we define a closed multiplication operation between tensors. A major motivation for considering this new type of tensor multiplication is to devise new types of factorizations for tensors which can then be used in applications.Specifically, this new multiplication allows us to introduce concepts such as tensor transpose, inverse, and identity, which lead to the notion of an orthogonal tensor. The multiplication also gives rise to a linear operator, and the null space of the resulting operator is identified. We extend the concept of outer products of vectors to outer products of matrices. All derivations are presented for third-order tensors. However, they can be easily extended to the order-p(p>3) case. We conclude with an application in image deblurring. 相似文献
16.
Image decoding optimization based on compressive sensing 总被引:1,自引:0,他引:1
Zhen ZhangYunhui Shi Dehui KongWenpeng Ding Baocai Yin 《Journal of Computational and Applied Mathematics》2011,236(5):812-818
Transform-based image codec follows the basic principle: the reconstructed quality is decided by the quantization level. Compressive sensing (CS) breaks the limit and states that sparse signals can be perfectly recovered from incomplete or even corrupted information by solving convex optimization. Under the same acquisition of images, if images are represented sparsely enough, they can be reconstructed more accurately by CS recovery than inverse transform. So, in this paper, we utilize a modified TV operator to enhance image sparse representation and reconstruction accuracy, and we acquire image information from transform coefficients corrupted by quantization noise. We can reconstruct the images by CS recovery instead of inverse transform. A CS-based JPEG decoding scheme is obtained and experimental results demonstrate that the proposed methods significantly improve the PSNR and visual quality of reconstructed images compared with original JPEG decoder. 相似文献
17.
Numerical Algorithms - In this paper, we consider the generalized nonnegative tensor factorization (GNTF) problem, which arises in multiple-tissue gene expression and multi-target tracking. Based... 相似文献
18.
《Journal of Computational and Applied Mathematics》2012,236(5):812-818
Transform-based image codec follows the basic principle: the reconstructed quality is decided by the quantization level. Compressive sensing (CS) breaks the limit and states that sparse signals can be perfectly recovered from incomplete or even corrupted information by solving convex optimization. Under the same acquisition of images, if images are represented sparsely enough, they can be reconstructed more accurately by CS recovery than inverse transform. So, in this paper, we utilize a modified TV operator to enhance image sparse representation and reconstruction accuracy, and we acquire image information from transform coefficients corrupted by quantization noise. We can reconstruct the images by CS recovery instead of inverse transform. A CS-based JPEG decoding scheme is obtained and experimental results demonstrate that the proposed methods significantly improve the PSNR and visual quality of reconstructed images compared with original JPEG decoder. 相似文献
19.
稀疏表示是近年来新兴的一种数据表示方法,是对人类大脑皮层编码机制的模拟。稀疏表示以其良好的鲁棒性、抗干扰能力、可解释性和判别性等优势,广泛应用于模式识别领域。基于稀疏表示的分类器在人脸识别领域取得了令人惊喜的成就,它将训练样本看成字典,寻求测试样本在字典下的最稀疏的表示,即用尽可能少的训练样本的线性组合来重构测试样本。但是经典的基于稀疏表示的分类器没有考虑训练样本的类别信息,以致被选中的训练样本来自许多类,不利于分类,因此基于组稀疏的分类器被提出。组稀疏方法考虑了训练样本的类别相似性,其目的是用尽可能少类别的训练样本来表示测试样本,然而这类方法的缺点是同类的训练样本或者同时被选中或者同时被丢弃。在实际中,人脸受到光照、表情、姿势甚至遮挡等因素的影响,样本之间关系比较复杂,因此最后介绍局部加权组结构稀疏表示方法。该方法尽量用来自于与测试样本相似的类的训练样本和来自测试样本邻域的训练样本来表示测试样本,以减轻不相关类的干扰,并使得表示更稀疏和更具判别性。 相似文献
20.
We design, analyse and test a class of incomplete orthogonal factorization preconditioners constructed from Givens rotations, incorporating some dropping strategies and updating tricks, for the solution of large sparse systems of linear equations. Comprehensive accounts about how the preconditioners are coded, what storage is required and how the computation is executed for a given accuracy are presented. A number of numerical experiments show that these preconditioners are competitive with standard incomplete triangular factorization preconditioners when they are applied to accelerate Krylov subspace iteration methods such as GMRES and BiCGSTAB. 相似文献