The choice of relaxation parameter in the projected successive overrelaxation (PSOR) method for nonnegative quadratic programming problems is problem-dependent. We present novel adaptive PSOR algorithms that adaptivel...
详细信息
The choice of relaxation parameter in the projected successive overrelaxation (PSOR) method for nonnegative quadratic programming problems is problem-dependent. We present novel adaptive PSOR algorithms that adaptively control the relaxation parameter using the Wolfe conditions. The method and its variants can be applied to various problems without requiring additional assumptions, barring the positive semidefiniteness concerning the matrix that defines the objective function, and the cost for updating the parameter is negligible in the whole iteration. Numerical experiments show that the proposed methods often perform comparably to (or sometimes superior to) the PSOR method with a nearly optimal relaxation parameter.
In neural computation and statistical learning, there are many problems involving quadraticprogramming with nonnegativity constraints. In this paper, we study nonnegative quadratic programming (NQP) and develop an al...
详细信息
ISBN:
(纸本)9781538635247
In neural computation and statistical learning, there are many problems involving quadraticprogramming with nonnegativity constraints. In this paper, we study nonnegative quadratic programming (NQP) and develop an alternative multiplicative update algorithm for this problem by constructing new auxiliary functions. We prove that the new NQP algorithm can minimize the objective function gradually at each iteration. Similar to the well-known Fei Sha's multiplicative update NQP algorithm, the proposed one also has a simple close form and does not need to set any heuristics or other parameters that must be turned to ensure convergence. We illustrate the proposed multiplicative update NQP algorithm is comparable to Fei Sha's one in term of performance.
Diffusion is a fundamental graph procedure and has been a basic building block in a wide range of theoretical and empirical applications such as graph partitioning and semi-supervised learning on graphs. In this paper...
详细信息
ISBN:
(纸本)9781665420556
Diffusion is a fundamental graph procedure and has been a basic building block in a wide range of theoretical and empirical applications such as graph partitioning and semi-supervised learning on graphs. In this paper, we study computationally efficient diffusion primitives beyond random walk. We design an near-linear time randomized algorithm for the 2-norm flow diffusion problem, a recently proposed diffusion model based on network flow with demonstrated graph clustering related applications both in theory and in practice. Examples include finding locally-biased low conductance cuts. Using a known connection between the optimal dual solution of the flow diffusion problem and the local cut structure, our algorithm gives an alternative approach for finding such cuts in nearly linear time. From a technical point of view, our algorithm contributes a novel way of dealing with inequality constraints in graph optimization problems. It adapts the high-level algorithmic framework of nearly linear time Laplacian system solvers, but requires several new tools: vertex elimination under constraints, a new family of graph ultra-sparsifiers, and accelerated proximal gradient methods with inexact proximal mapping computation.
nonnegative least squares (NNLS) optimization is an important algorithmic component of many problems in science and engineering, including image segmentation, spectral deconvolution, and reconstruction of compressivel...
详细信息
ISBN:
(纸本)9781467381239
nonnegative least squares (NNLS) optimization is an important algorithmic component of many problems in science and engineering, including image segmentation, spectral deconvolution, and reconstruction of compressively sensed data. Each of these areas can benefit from high performance implementations suitable for embedded applications. Unfortunately, the NNLS problem has no solution expressible in closed-form, and many popular algorithms are not amenable to compact and scalable hardware implementation. Classical iterative algorithms generally have a per-iteration computational cost with cubic growth, and interdependencies which limit parallel approaches. In this paper we develop two efficient hardware architectures. One is based on a novel algorithm we develop in this paper specifically to reduce FPGA area consumption while preserving performance. We implement our architectures on a very small FPGA and apply them to reconstruction of a compressively sensed signal showing residual error results competitive with traditional algorithms.
Alternative least squares (ALS) algorithm is considered as a "work-horse" algorithm for general tensor factorizations. A common form of this algorithm for nonnegative tensor factorizations (NTF) is always co...
详细信息
Alternative least squares (ALS) algorithm is considered as a "work-horse" algorithm for general tensor factorizations. A common form of this algorithm for nonnegative tensor factorizations (NTF) is always combined with a nonlinear projection (rectifier) to enforce nonnegative entries during the estimation. Such simple modification often provides acceptable results for general data. However, this does not establish an appropriate ALS algorithm for NTF. This kind of ALS algorithm often converges slowly, or cannot converge to the desired solution, especially for collinear data. To this end, in this paper, we reinvestigate the nonnegative quadratic programming, propose a recursive method for solving this problem. Then, we formulate a novel ALS algorithm for NTF. The validity and high performance of the proposed algorithm has been confirmed for difficult benchmarks, and also in an application of object classification, and analysis of EEG signals.
暂无评论