Motivated by recent work on stochastic gradient descent methods, we develop two stochastic variants of greedy algorithms for possibly non-convex optimization problems with sparsity constraints. We prove linear convergence in expectation to the solution within a specified tolerance. This generalized framework applies to problems such as sparse signal recovery in compressed sensing, low-rank matrix recovery, and covariance matrix estimation, giving methods with provable convergence guarantees that often outperform their deterministic counterparts. We also analyze the settings where gradients and projections can only be computed approximately, and prove the methods are robust to these approximations. We include many numerical experiments which align with the theoretical analysis and demonstrate these improvements in several different settings.
We outline the GradMP method here, since it will be used as motivation for the work we propose. GradMP @cite_38 is a generalization of the CoSaMP @cite_29 that solves a wider class of sparse reconstruction problems. Like OMP, these methods consist of four main steps: i) form a signal proxy, ii) select a set of large entries of the proxy, iii) use those as the support estimation and estimate the signal via least-squares, and iv) prune the estimation and repeat. Methods like OMP and CoSaMP use the proxy @math ; more general methods like GradMP use the gradient @math (see @cite_38 for details). The analysis of GradMP depends on the restricted strong convexity and restricted strong smoothness properties as in Definitions and below, the first of which is motivated by a similar property introduced in @cite_30 . Under these assumptions, the authors prove linear convergence to the noise floor.
@cite_30 @cite_38 @cite_29
2950190315 2289917018
In this paper, we consider the problem of compressed sensing where the goal is to recover all sparse vectors using a small number of fixed linear measurements. For this problem, we propose a novel partial hard-thresholding operator that leads to a general family of iterative algorithms. While one extreme of the family yields well known hard thresholding algorithms like ITI and HTP[17, 10], the other end of the spectrum leads to a novel algorithm that we call Orthogonal Matching Pursuit with Replacement (OMPR). OMPR, like the classic greedy algorithm OMP, adds exactly one coordinate to the support at each iteration, based on the correlation with the current residual. However, unlike OMP, OMPR also removes one coordinate from the support. This simple change allows us to prove that OMPR has the best known guarantees for sparse recovery in terms of the Restricted Isometry Property (a condition on the measurement matrix). In contrast, OMP is known to have very weak performance guarantees under RIP. Given its simple structure, we are able to extend OMPR using locality sensitive hashing to get OMPR-Hash, the first provably sub-linear (in dimensionality) algorithm for sparse recovery. Our proof techniques are novel and flexible enough to also permit the tightest known analysis of popular iterative algorithms such as CoSaMP and Subspace Pursuit. We provide experimental results on large problems providing recovery for vectors of size up to million dimensions. We demonstrate that for large-scale problems our proposed methods are more robust and faster than existing methods. Orthogonal matching pursuit (OMP) is a commonly used algorithm for recovery sparse signals due to its low complexity and simple implementation. We analyze the convergence property of OMP based on the restricted isometry property (RIP), and show that the OMP algorithm can exactly recover an arbitrary K-sparse signal using K steps provided that the sampling matrix Φ satisfies the RIP with parameter . In addition, we also give the convergence analysis of OMP for the case of inaccurate measurements. Moreover, a variant of OMP, referred to as multi-candidate OMP (MOMP) algorithm, is proposed to recover sparse signals, which can further reduce the computational complexity of OMP. The key point of MOMP is that at each step it selects multi-candidates adding to the optimal atom set, whilst OMP only selects one atom. We also present the convergence analysis of MOMP using the RIP. Finally, we testify the performance of the proposed algorithm using several numerical experiments. Abstract It is now well-known that one can reconstruct sparse or compressible signals accurately from a very limited number of measurements, possibly contaminated with noise. This technique known as “compressed sensing” or “compressive sampling” relies on properties of the sensing matrix such as the restricted isometry property . In this Note, we establish new results about the accuracy of the reconstruction from undersampled measurements which improve on earlier estimates, and have the advantage of being more elegant. To cite this article: E.J. Candes, C. R. Acad. Sci. Paris, Ser. I 346 (2008). Hybrid multiple input multiple output (MIMO) systems consist of an analog beamformer with large antenna arrays followed by a digital MIMO processor. Channel estimation for hybrid MIMO systems in millimeter wave (mm-wave) communications is challenging because of the large antenna array and the low signal-to-noise ratio (SNR) before beamforming. In this paper, we propose an open-loop channel estimator for mm-wave hybrid MIMO systems exploiting the sparse nature of mm-wave channels. A sparse signal recovery problem is formulated for channel estimation and solved by the orthogonal matching pursuit (OMP) based methods. A modification of the OMP algorithm, called the multi-grid (MG) OMP, is proposed. It is shown that the MG-OMP can significantly reduce the computational load of the OMP method. A process for designing the training beams is also developed. Specifically, given the analog training beams the baseband processor for beam training is designed. Simulation results demonstrate the advantage of the OMP based methods over the conventional least squares (LS) method and the efficiency of the MG-OMP over the original OMP.