Improved Bounds for RIC in Compressed Sensing
This paper improves bounds for restricted isometry constant (RIC) in compressed sensing. Let \phi be a m*n real matrix and k be a positive integer with k
l1-minimization
Error Forgetting of Bregman Iteration
This short article analyzes an interesting property of the Bregman iterative procedure, which is equivalent to the augmented Lagrangian method after a change of variable, for minimizing a convex piece-wise linear function J(x) subject to linear constraints Ax=b. The procedure obtains its solution by solving a sequence of unconstrained subproblems of minimizing J(x)+1/2||Ax-b^k||^2, where b^k … Read more
Solving Basis Pursuit: Heuristic Optimality Check and Solver Comparison
The problem of finding a minimum l^1-norm solution to an underdetermined linear system is an important problem in compressed sensing, where it is also known as basis pursuit. We propose a heuristic optimality check as a general tool for l^1-minimization, which often allows for early termination by “guessing” a primal-dual optimal pair based on an … Read more
On partially sparse recovery
In this paper we consider the problem of recovering a partially sparse solution of an underdetermined system of linear equations by minimizing the l1-norm of the part of the solution vector which is known to be sparse. Such a problem is closely related to the classical problem in Compressed Sensing where the l1-norm of the … Read more
Computation of sparse low degree interpolating polynomials and their application to derivative-free optimization
Interpolation-based trust-region methods are an important class of algorithms for Derivative-Free Optimization which rely on locally approximating an objective function by quadratic polynomial interpolation models, frequently built from less points than there are basis components. Often, in practical applications, the contribution of the problem variables to the objective function is such that many pairwise correlations … Read more
On partially sparse recovery
In this paper we consider the problem of recovering a partially sparse solution of an underdetermined system of linear equations by minimizing the l1-norm of the part of the solution vector which is known to be sparse. Such a problem is closely related to the classical problem in Compressed Sensing where the l1-norm of the … Read more
Computation of sparse low degree interpolating polynomials and their application to derivative-free optimization
Interpolation-based trust-region methods are an important class of algorithms for Derivative-Free Optimization which rely on locally approximating an objective function by quadratic polynomial interpolation models, frequently built from less points than there are basis components. Often, in practical applications, the contribution of the problem variables to the objective function is such that many pairwise correlations … Read more
L1 Minimization via Randomized First Order Algorithms
In this paper we propose randomized first-order algorithms for solving bilinear saddle points problems. Our developments are motivated by the need for sublinear time algorithms to solve large-scale parametric bilinear saddle point problems where cheap online assessment of solution quality is crucial. We present the theoretical efficiency estimates of our algorithms and discuss a number … Read more
A First-Order Augmented Lagrangian Method for Compressed Sensing
We propose a First-order Augmented Lagrangian algorithm (FAL) for solving the basis pursuit problem. FAL computes a solution to this problem by inexactly solving a sequence of L1-regularized least squares sub-problems. These sub-problems are solved using an infinite memory proximal gradient algorithm wherein each update reduces to “shrinkage” or constrained “shrinkage”. We show that FAL … Read more
Sparse Signal Reconstruction via Iterative Support Detection
We present a novel sparse signal reconstruction method “ISD”, aiming to achieve fast reconstruction and a reduced requirement on the number of measurements compared to the classical l_1 minimization approach. ISD addresses failed reconstructions of l_1 minimization due to insufficient measurements. It estimates a support set I from a current reconstruction and obtains a new … Read more