Revisiting compressed sensing: exploiting the efficiency of simplex and sparsification methods

We propose two approaches to solve large-scale compressed sensing problems. The first approach uses the parametric simplex method to recover very sparse signals by taking a small number of simplex pivots, while the second approach reformulates the problem using Kronecker products to achieve faster computation via a sparser problem formulation. In particular, we focus on the computational aspects of these methods in compressed sensing. For the first approach, if the true signal is very sparse and we initialize our solution to be the zero vector, then a customized parametric simplex method usually takes a small number of iterations to converge. Our numerical studies show that this approach is 10 times faster than state-of-the-art methods for recovering very sparse signals. The second approach can be used when the sensing matrix is the Kronecker product of two smaller matrices. We show that the best-known sufficient condition for the Kronecker compressed sensing (KCS) strategy to obtain a perfect recovery is more restrictive than the corresponding condition if using the first approach. However, KCS can be formulated as a linear program with a very sparse constraint matrix, whereas the first approach involves a completely dense constraint matrix. Hence, algorithms that benefit from sparse problem representation, such as interior point methods (IPMs), are expected to have computational advantages for the KCS problem. We numerically demonstrate that KCS combined with IPMs is up to 10 times faster than vanilla IPMs and state-of-the-art methods such as \(\ell _1\_\ell _s\) and Mirror Prox regardless of the sparsity level or problem size.     

Sharp Recovery Bounds for Convex Demixing,with Applications

Demixing refers to the challenge of identifying two structured signals given only the sum of the two signals and prior information about their structures. Examples include the problem of separating a signal that is sparse with respect to one basis from a signal that is sparse with respect to a second basis, and the problem of decomposing an observed matrix into a low-rank matrix plus a sparse matrix. This paper describes and analyzes a framework, based on convex optimization, for solving these demixing problems, and many others. This work introduces a randomized signal model that ensures that the two structures are incoherent, i.e., generically oriented. For an observation from this model, this approach identifies a summary statistic that reflects the complexity of a particular signal. The difficulty of separating two structured, incoherent signals depends only on the total complexity of the two structures. Some applications include (1) demixing two signals that are sparse in mutually incoherent bases, (2) decoding spread-spectrum transmissions in the presence of impulsive errors, and (3) removing sparse corruptions from a low-rank matrix. In each case, the theoretical analysis of the convex demixing method closely matches its empirical behavior.     

A feasible method for optimization with orthogonality constraints

Minimization with orthogonality constraints (e.g., $X^\top X = I$ ) and/or spherical constraints (e.g., $\Vert x\Vert _2 = 1$ ) has wide applications in polynomial optimization, combinatorial optimization, eigenvalue problems, sparse PCA, p-harmonic flows, 1-bit compressive sensing, matrix rank minimization, etc. These problems are difficult because the constraints are not only non-convex but numerically expensive to preserve during iterations. To deal with these difficulties, we apply the Cayley transform—a Crank-Nicolson-like update scheme—to preserve the constraints and based on it, develop curvilinear search algorithms with lower flops compared to those based on projections and geodesics. The efficiency of the proposed algorithms is demonstrated on a variety of test problems. In particular, for the maxcut problem, it exactly solves a decomposition formulation for the SDP relaxation. For polynomial optimization, nearest correlation matrix estimation and extreme eigenvalue problems, the proposed algorithms run very fast and return solutions no worse than those from their state-of-the-art algorithms. For the quadratic assignment problem, a gap 0.842 % to the best known solution on the largest problem “tai256c” in QAPLIB can be reached in 5 min on a typical laptop.     

Greedy expansions in convex optimization

This paper is a follow-up to the author’s previous paper on convex optimization. In that paper we began the process of adjusting greedy-type algorithms from nonlinear approximation for finding sparse solutions of convex optimization problems. We modified there the three most popular greedy algorithms in nonlinear approximation in Banach spaces-Weak Chebyshev Greedy Algorithm, Weak Greedy Algorithm with Free Relaxation, and Weak Relaxed Greedy Algorithm-for solving convex optimization problems. We continue to study sparse approximate solutions to convex optimization problems. It is known that in many engineering applications researchers are interested in an approximate solution of an optimization problem as a linear combination of elements from a given system of elements. There is an increasing interest in building such sparse approximate solutions using different greedy-type algorithms. In this paper we concentrate on greedy algorithms that provide expansions, which means that the approximant at the mth iteration is equal to the sum of the approximant from the previous, (m ? 1)th, iteration and one element from the dictionary with an appropriate coefficient. The problem of greedy expansions of elements of a Banach space is well studied in nonlinear approximation theory. At first glance the setting of a problem of expansion of a given element and the setting of the problem of expansion in an optimization problem are very different. However, it turns out that the same technique can be used for solving both problems. We show how the technique developed in nonlinear approximation theory, in particular, the greedy expansions technique, can be adjusted for finding a sparse solution of an optimization problem given by an expansion with respect to a given dictionary.     

Learning the coordinate gradients

In this paper we study the problem of learning the gradient function with application to variable selection and determining variable covariation. Firstly, we propose a novel unifying framework for coordinate gradient learning from the perspective of multi-task learning. Various variable selection methods can be regarded as special instances of this framework. Secondly, we formulate the dual problems of gradient learning with general loss functions. This enables the direct application of standard optimization toolboxes to the case of gradient learning. For instance, gradient learning with SVM loss can be solved by quadratic programming (QP) routines. Thirdly, we propose a novel gradient learning formulation which can be cast as a learning the kernel matrix problem. Its relation with sparse regularization is highlighted. A semi-infinite linear programming (SILP) approach and an iterative optimization approach are proposed to efficiently solve this problem. Finally, we validate our proposed approaches on both synthetic and real datasets.     

Optimization of unconstrained functions with sparse hessian matrices-newton-type methods

Newton-type methods for unconstrained optimization problems have been very successful when coupled with a modified Cholesky factorization to take into account the possible lack of positive-definiteness in the Hessian matrix. In this paper we discuss the application of these method to large problems that have a sparse Hessian matrix whose sparsity is known a priori. Quite often it is difficult, if not impossible, to obtain an analytic representation of the Hessian matrix. Determining the Hessian matrix by the standard method of finite-differences is costly in terms of gradient evaluations for large problems. Automatic procedures that reduce the number of gradient evaluations by exploiting sparsity are examined and a new procedure is suggested. Once a sparse approximation to the Hessian matrix has been obtained, there still remains the problem of solving a sparse linear system of equations at each iteration. A modified Cholesky factorization can be used. However, many additional nonzeros (fill-in) may be created in the factors, and storage problems may arise. One way of approaching this problem is to ignore fill-in in a systematic manner. Such technique are calledpartial factorization schemes. Various existing partial factorization are analyzed and three new ones are developed. The above algorithms were tested on a set of problems. The overall conclusions were that these methods perfom well in practice.     

压缩感知和稀疏优化简介

介绍压缩感知和稀疏优化的基本概念、理论基础和算法概要. 压缩感知利用原始信号的稀疏性,从远少于信号元素个数的测量出发,通过求解稀疏优化问题来恢复完整的原始稀疏信号. 通过一个小例子展示这一过程,并以此说明压缩感知和稀疏优化的基本理念. 接着简要介绍用以保证l₁凸优化恢复稀疏信号的零空间性质和RIP条件. 最后介绍求解稀疏优化的几个经典算法.     

A nonconvex formulation for low rank subspace clustering: algorithms and convergence analysis

We consider the problem of subspace clustering with data that is potentially corrupted by both dense noise and sparse gross errors. In particular, we study a recently proposed low rank subspace clustering approach based on a nonconvex modeling formulation. This formulation includes a nonconvex spectral function in the objective function that makes the optimization task challenging, e.g., it is unknown whether the alternating direction method of multipliers (ADMM) framework proposed to solve the nonconvex model formulation is provably convergent. In this paper, we establish that the spectral function is differentiable and give a formula for computing the derivative. Moreover, we show that the derivative of the spectral function is Lipschitz continuous and provide an explicit value for the Lipschitz constant. These facts are then used to provide a lower bound for how the penalty parameter in the ADMM method should be chosen. As long as the penalty parameter is chosen according to this bound, we show that the ADMM algorithm computes iterates that have a limit point satisfying first-order optimality conditions. We also present a second strategy for solving the nonconvex problem that is based on proximal gradient calculations. The convergence and performance of the algorithms is verified through experiments on real data from face and digit clustering and motion segmentation.     

Efficient algorithms for robust and stable principal component pursuit problems

The problem of recovering a low-rank matrix from a set of observations corrupted with gross sparse error is known as the robust principal component analysis (RPCA) and has many applications in computer vision, image processing and web data ranking. It has been shown that under certain conditions, the solution to the NP-hard RPCA problem can be obtained by solving a convex optimization problem, namely the robust principal component pursuit (RPCP). Moreover, if the observed data matrix has also been corrupted by a dense noise matrix in addition to gross sparse error, then the stable principal component pursuit (SPCP) problem is solved to recover the low-rank matrix. In this paper, we develop efficient algorithms with provable iteration complexity bounds for solving RPCP and SPCP. Numerical results on problems with millions of variables and constraints such as foreground extraction from surveillance video, shadow and specularity removal from face images and video denoising from heavily corrupted data show that our algorithms are competitive to current state-of-the-art solvers for RPCP and SPCP in terms of accuracy and speed.     

Optimal server resource reservation policies for priority classes of users under cyclic non-homogeneous markov modeling

Resource availability optimization is studied on a server–client system where different users are partitioned into priority classes. The aim is to provide higher resource availability according to the priority of each class. For this purpose, resource reservation is modeled by a homogeneous continuous time Markov chain (CTMC), but also by a cyclic non-homogeneous Markov chain (CNHMC) as there is a cyclic behavior of the users’ requests for resources. The contribution of the work presented consists in the formulation of a multiobjective optimization problem for both the above cases that aims to determine the optimal resource reservation policy providing higher levels of resource availability for all classes. The optimization problem is solved either with known methods or with a proposed kind of heuristic algorithm. Finally, explicit generalized approximate inverse preconditioning methods are adopted for solving efficiently sparse linear systems that are derived, in order to compute resource availability.     

Sparse Linear Least Squares Problems in Optimization

Numerical and computational aspects of direct methods for largeand sparseleast squares problems are considered. After a brief survey of the most oftenused methods, we summarize the important conclusions made from anumerical comparison in matlab. Significantly improved algorithms haveduring the last 10-15 years made sparse QR factorization attractive, andcompetitive to previously recommended alternatives. Of particular importanceis the multifrontal approach, characterized by low fill-in, dense subproblemsand naturally implemented parallelism. We describe a Householder multifrontalscheme and its implementation on sequential and parallel computers. Availablesoftware has in practice a great influence on the choice of numericalalgorithms. Less appropriate algorithms are thus often used solely because ofexisting software packages. We briefly survey softwarepackages for the solution of sparse linear least squares problems. Finally,we focus on various applications from optimization, leading to the solution oflarge and sparse linear least squares problems. In particular, we concentrateon the important case where the coefficient matrix is a fixed general sparsematrix with a variable diagonal matrix below. Inner point methods forconstrained linear least squares problems give, for example, rise to suchsubproblems. Important gains can be made by taking advantage of structure.Closely related is also the choice of numerical method for these subproblems.We discuss why the less accurate normal equations tend to be sufficient inmany applications.     

Wavelet-like bases for thin-wire integral equations in electromagnetics

In this paper, wavelets are used in solving, by the method of moments, a modified version of the thin-wire electric field integral equation, in frequency domain. The time domain electromagnetic quantities, are obtained by using the inverse discrete fast Fourier transform. The retarded scalar electric and vector magnetic potentials are employed in order to obtain the integral formulation. The discretized model generated by applying the direct method of moments via point-matching procedure, results in a linear system with a dense matrix which have to be solved for each frequency of the Fourier spectrum of the time domain impressed source. Therefore, orthogonal wavelet-like basis transform is used to sparsify the moment matrix. In particular, dyadic and M-band wavelet transforms have been adopted, so generating different sparse matrix structures. This leads to an efficient solution in solving the resulting sparse matrix equation. Moreover, a wavelet preconditioner is used to accelerate the convergence rate of the iterative solver employed. These numerical features are used in analyzing the transient behavior of a lightning protection system. In particular, the transient performance of the earth termination system of a lightning protection system or of the earth electrode of an electric power substation, during its operation is focused. The numerical results, obtained by running a complex structure, are discussed and the features of the used method are underlined.     

Comparison of preconditioned Krylov subspace iteration methods for PDE-constrained optimization problems

The governing dynamics of fluid flow is stated as a system of partial differential equations referred to as the Navier-Stokes system. In industrial and scientific applications, fluid flow control becomes an optimization problem where the governing partial differential equations of the fluid flow are stated as constraints. When discretized, the optimal control of the Navier-Stokes equations leads to large sparse saddle point systems in two levels. In this paper, we consider distributed optimal control for the Stokes system and test the particular case when the arising linear system can be compressed after eliminating the control function. In that case, a system arises in a form which enables the application of an efficient block matrix preconditioner that previously has been applied to solve complex-valued systems in real arithmetic. Under certain conditions, the condition number of the so preconditioned matrix is bounded by 2. The numerical and computational efficiency of the method in terms of number of iterations and execution time is favorably compared with other published methods.     

Numerical solution of the acoustic wave equation using Raviart–Thomas elements

In this paper we discuss the numerical approximation of the displacement form of the acoustic wave equation using mixed finite elements. The mixed formulation allows for approximation of both displacement and pressure at each time step, without the need for post-processing. Lowest-order and next-to-lowest-order Raviart–Thomas elements are used for the spatial discretization, and centered finite differences are used to advance in time. Use of these Raviart–Thomas elements results in a diagonal mass matrix for resolution of pressure, and a mass matrix for the displacement variable that is sparse with a simple structure. Convergence results for a model problem are provided, as are numerical results for a two-dimensional problem with a point source.     

低秩稀疏矩阵恢复的快速非单调交替极小化方法

针对低秩稀疏矩阵恢复问题的一个非凸优化模型,本文提出了一种快速非单调交替极小化方法.主要思想是对低秩矩阵部分采用交替极小化方法,对稀疏矩阵部分采用非单调线搜索技术来分别进行迭代更新.非单调线搜索技术是将单步下降放宽为多步下降,从而提高了计算效率.文中还给出了新算法的收敛性分析.最后,通过数值实验的比较表明,矩阵恢复的非单调交替极小化方法比原单调类方法更有效.     

Sparse null basis computations in structural optimization

Summary We study the computation of sparse null bases of equilibrium matrices in the context of the force method in structural optimization. Two classes of structural problems are considered. For the class of rigid jointed skeletal structures, we use a partitioning method suggested by Henderson and Maunder to partition the problem into a set of independent null basis computations. For the class of structures represented by a continuum, we compute a sizable fraction of the null vectors in a basis from a consideration of the finite element formulation and the bipartite graph of the equilibrium matrix. The remaining null vectors are computed by the triangular algorithm in [6]. The new algorithms find sparser bases than the triangular algorithm and are also faster.This research was partially supported by NSF grant CCR-8701723 and AFOSR grant 88-0161     

A tensor-based dictionary learning approach to tomographic image reconstruction

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.     

Optimization challenges in the structured low rank approximation problem

In this paper we illustrate some optimization challenges in the structured low rank approximation (SLRA) problem. SLRA can be described as the problem of finding a low rank approximation of an observed matrix which has the same structure as this matrix (such as Hankel). We demonstrate that the optimization problem arising is typically very difficult: in particular, the objective function is multiextremal even for simple cases. The main theme of the paper is to suggest that the difficulties described in approximating a solution of the SLRA problem open huge possibilities for the application of stochastic methods of global optimization.     

Exploiting sparsity in linear and nonlinear matrix inequalities via positive semidefinite matrix completion

A basic framework for exploiting sparsity via positive semidefinite matrix completion is presented for an optimization problem with linear and nonlinear matrix inequalities. The sparsity, characterized with a chordal graph structure, can be detected in the variable matrix or in a linear or nonlinear matrix-inequality constraint of the problem. We classify the sparsity in two types, the domain-space sparsity (d-space sparsity) for the symmetric matrix variable in the objective and/or constraint functions of the problem, which is required to be positive semidefinite, and the range-space sparsity (r-space sparsity) for a linear or nonlinear matrix-inequality constraint of the problem. Four conversion methods are proposed in this framework: two for exploiting the d-space sparsity and the other two for exploiting the r-space sparsity. When applied to a polynomial semidefinite program (SDP), these conversion methods enhance the structured sparsity of the problem called the correlative sparsity. As a result, the resulting polynomial SDP can be solved more effectively by applying the sparse SDP relaxation. Preliminary numerical results on the conversion methods indicate their potential for improving the efficiency of solving various problems.     

A Structured Reduced Sequential Quadratic Programming and Its Application to a Shape Design Problem

The objective of this work is to solve a model one dimensional duct design problem using a particular optimization method. The design problem is formulated as an equality constrained optimization, called all at once method, so that the analysis problem is not solved until the optimal design is reached. Furthermore, the sparsity structure in the Jacobian of the linearized constraints is exploited by decomposing the variables into the design and flow parts. To achieve this, sequential quadratic programming with BFGS update for the reduced Hessian of the Lagrangian function is used with the variable reduction method which preserves the structure of the Jacobian in representing the null space basis matrix. By updating the reduced Hessians of which the dimension is the number of design variables, the storage requirement for the Hessians is reduced by a large amount. In addition, the flow part of the Jacobian can be computed analytically.The algorithm with a line search globalization is described. A global and local analysis is provided with a modification of the paper by Byrd and Nocedal [Mathematical Programming 49(1991) pp 285-323] in which they analyzed a similar algorithm with the orthogonal factorization method which assumes the orthogonality of the null space basis matrix. Numerical results are obtained and compared favorably with results from the black box method, unconstrained optimization formulation.