We present a proximal quasi-Newton method in which the approximation of the Hessian has the special format of “identity minus rank one” (IMRO) in each iteration. The proposed structure enables us to effectively recover the proximal point. The algorithm is applied to @math -regularized least squares problems arising in many applications including sparse recovery in compressive sensing, machine learning, and statistics. Our numerical experiment suggests that the proposed technique competes favorably with other state-of-the-art solvers for this class of problems. We also provide a complexity analysis for variants of IMRO, showing that it matches known best bounds.
Algorithms that rely solely on the function value and the gradient of each iterate are referred to as first-order methods. Due to the large size of the problems arising in compressive sensing, first-order methods are more desirable in sparse recovery. There are numerous gradient-based first-order algorithms proposed for sparse recovery, see for example @cite_27 @cite_5 @cite_36 @cite_49 @cite_33 @cite_19 @cite_53 @cite_9 .
@cite_33 @cite_36 @cite_53 @cite_9 @cite_19 @cite_27 @cite_49 @cite_5
2406740263 2107861471 2130979540 2964167436
The goal of sparse recovery is to recover a k-sparse signal x e Rn from (possibly noisy) linear measurements of the form y = Ax, where A e Rmxn describes the measurement process. Standard results in compressive sensing show that it is possible to recover the signal x from m = O(k log(n k)) measurements, and that this bound is tight. The framework of model-based compressive sensing [BCDH10] overcomes the lower bound and reduces the number of measurements further to O(k) by limiting the supports of x to a subset M of the (nk) possible supports. This has led to many measurement-efficient algorithms for a wide variety of signal models, including block-sparsity and tree-sparsity. Unfortunately, extending the framework to other, more general models has been stymied by the following obstacle: for the framework to apply, one needs an algorithm that, given a signal x, solves the following optimization problem exactly: [EQUATION] (here x[n] denotes the projection of x on coordinates not in Ω). However, an approximation algorithm for this optimization task is not sufficient. Since many problems of this form are not known to have exact polynomial-time algorithms, this requirement poses an obstacle for extending the framework to a richer class of models. In this paper, we remove this obstacle and show how to extend the model-based compressive sensing framework so that it requires only approximate solutions to the aforementioned optimization problems. Interestingly, our extension requires the existence of approximation algorithms for both the maximization and the minimization variants of the optimization problem. Further, we apply our framework to the Constrained Earth Mover's Distance (CEMD) model introduced in [SHI13], obtaining a sparse recovery scheme that uses significantly less than O(k log(n k)) measurements. This is the first non-trivial theoretical bound for this model, since the validation of the approach presented in [SHI13] was purely empirical. The result is obtained by designing a novel approximation algorithm for the maximization version of the problem and proving approximation guarantees for the minimization algorithm described in [SHI13]. It is now well understood that (1) it is possible to reconstruct sparse signals exactly from what appear to be highly incomplete sets of linear measurements and (2) that this can be done by constrained l1 minimization. In this paper, we study a novel method for sparse signal recovery that in many situations outperforms l1 minimization in the sense that substantially fewer measurements are needed for exact recovery. The algorithm consists of solving a sequence of weighted l1-minimization problems where the weights used for the next iteration are computed from the value of the current solution. We present a series of experiments demonstrating the remarkable performance and broad applicability of this algorithm in the areas of sparse signal recovery, statistical estimation, error correction and image processing. Interestingly, superior gains are also achieved when our method is applied to recover signals with assumed near-sparsity in overcomplete representations—not by reweighting the l1 norm of the coefficient sequence as is common, but by reweighting the l1 norm of the transformed object. An immediate consequence is the possibility of highly efficient data acquisition protocols by improving on a technique known as Compressive Sensing. We consider the approximate sparse recovery problem, where the goal is to (approximately) recover a high-dimensional vector xisinRopfn from its lower-dimensional sketch AxisinRopfm. Specifically, we focus on the sparse recovery problem in the L1 norm: for a parameter k, given the sketch Ax, compute an approximation xcirc of x such that the L1 approximation error parx-xcircpar1 is close to minx' parx-x'par1, where x' ranges over all vectors with at most k terms. The sparse recovery problem has been subject to extensive research over the last few years. Many solutions to this problem have been discovered, achieving different trade-offs between various attributes, such as the sketch length, encoding and recovery times. In this paper we provide a sparse recovery scheme which achieves close to optimal performance on virtually all attributes (see Figure 1). In particular, this is the first recovery scheme that guarantees O(k log(n k)) sketch length, and near-linear O(n log (n k)) recovery time simultaneously. It also features low encoding and update times, and is noise-resilient. Most of the existing sparse-recovery methods assume a static system: the signal is a finite-length vector for which a fixed set of measurements and sparse representation are available and an l1 problem is solved for the reconstruction. However, the same representation and reconstruction framework is not readily applicable in a streaming system: the signal changes over time, and it is measured and reconstructed sequentially over small intervals. This is particularly desired when dividing signals into disjoint blocks and processing each block separately is infeasible or inefficient. In this paper, we discuss two streaming systems and a new homotopy algorithm for quickly solving the associated l1 problems: 1) recovery of smooth, time-varying signals for which, instead of using block transforms, we use lapped orthogonal transforms for sparse representation and 2) recovery of sparse, time-varying signals that follows a linear dynamic model. For both systems, we iteratively process measurements over a sliding interval and solve a weighted l1-norm minimization problem for estimating sparse coefficients. Since we estimate overlapping portions of the signal while adding and removing measurements, instead of solving a new l1 program as the system changes, we use available signal estimates as starting point in a homotopy formulation and update the solution in a few simple steps. We demonstrate with numerical experiments that our proposed streaming recovery framework provides better reconstruction compared to the methods that represent and reconstruct signals as independent, disjoint blocks, and that our proposed homotopy algorithm updates the solution faster than the current state-of-the-art solvers.