About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
IEEE Trans. Inf. Theory
Paper
Linear convergence of stochastic iterative greedy algorithms with sparse constraints
Abstract
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 convergence1 in expectation to the solution within a specified tolerance. This generalized framework is specialized to the problems of sparse signal recovery in compressed sensing and low-rank matrix recovery, 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.