text: 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.
  @cite_30: High-dimensional statistical inference deals with models in which the the number of parameters p is comparable to or larger than the sample size n. Since it is usually impossible to obtain consistent procedures unless @math , a line of recent work has studied models with various types of low-dimensional structure, including sparse vectors, sparse and structured matrices, low-rank matrices and combinations thereof. In such settings, a general approach to estimation is to solve a regularized optimization problem, which combines a loss function measuring how well the model fits the data with some regularization function that encourages the assumed structure. This paper provides a unified framework for establishing consistency and convergence rates for such regularized M-estimators under high-dimensional scaling. We state one main theorem and show how it can be used to re-derive some existing results, and also to obtain a number of new results on consistency and convergence rates, in both @math -error and related norms. Our analysis also identifies two key properties of loss and regularization functions, referred to as restricted strong convexity and decomposability, that ensure corresponding regularized M-estimators have fast convergence rates and which are optimal in many well-studied cases.
  @cite_38: 
  @cite_29: Abstract Compressive sampling offers a new paradigm for acquiring signals that are compressible with respect to an orthonormal basis. The major algorithmic challenge in compressive sampling is to approximate a compressible signal from noisy samples. This paper describes a new iterative recovery algorithm called CoSaMP that delivers the same guarantees as the best optimization-based approaches. Moreover, this algorithm offers rigorous bounds on computational cost and storage. It is likely to be extremely efficient for practical problems because it requires only matrix–vector multiplies with the sampling matrix. For compressible signals, the running time is just O ( N log 2 N ) , where N is the length of the signal.
summary: 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.