Coordinate descent optimization for l 1 minimization with application to compressed sensing; a greedy algorithm

By Yingying Li, Stanley J. Osher. 2009

190 citations recorded by the source corpus.

Subfields: Aerospace Engineering, Artificial Intelligence, Computational Mechanics, Mathematical Optimization, Information Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Aerospace Engineering

In Artificial Intelligence

In Computational Mechanics

In Mathematical Optimization

In Information Theory

Citations in the corpus

Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function (2011, background): “While they seem to have never belonged to the mainstream focus of the optimization community, a renewed interest in CD methods was sparked recently by their successful application in several areas—training support vector machines in machine learning [5, 3, 17, 28, 29], optimization [9, 23, 21, 20, 3”
Parallel coordinate descent methods for big data optimization (2012, methodology): “Indeed, the size of problems arising in ﬁelds such as machine learning [1], network analysis [29], PDEs [27], truss topology design [15] and compressed sensing [5] usually grows with our capacity to solve them, and is projected to grow dramatically in the next decade.”
Separable approximations and decomposition methods for the augmented Lagrangian (2013, methodology): “zed in [4, 23, 35, 5, 32], primal-dual methods in [33, 35] and inexact methods in [36]. The methods are used in a number of applications, including linear classication [8, 3, 35], compressed sensing [10], truss topology design [21], solving linear systems of equations [9] and group lasso problems [2”
Structured sparse coding via lateral inhibition (2011, methodology): “The coordinate selection can be done by picking the entry with the largest gradient Wu and Lange (2008), or by approximating the value of the energy after the line search Li and Osher (2009).”
A Unified Primal-Dual Algorithm Framework Based on Bregman Iteration (2010, methodology): “Note that the first subproblem can be also solved by other methods, such as the iterative shrinkage by Daubechies, De Frise and De Mol in [21], GPSR[27], `(1) ls [36], a greedy algorithm [38], FISTA [3] and NESTA [4].”
Parallel Coordinate Descent Newton Method for Efficient $\ell_1$-Regularized Minimization (2013, background): “…arise in a wide range of applications including sparse logistic regression (Ng, 2004), 1 -regularized 2 -loss SVM (Chang et al., 2008), compressed sensing (Li and Osher, 2009), image coding (Lee et al., 2009), face recognition (Wright et al., 2009), and object tracking (Mei and Ling, 2011).”
On the complexity analysis of randomized block-coordinate descent methods (2013, methodology): “Block-coordinate descent (BCD) methods and their variants have been successfully applied to solve various large-scale optimization problems (see, for example, [22, 4, 18, 19, 20, 21, 9, 23]).”
Randomized Block Coordinate Descent for Online and Stochastic Optimization (2014, background): “For stronglyconvex functions, by reducing the variance of stochastic gradients, we show that ORBCD can converge at a geometric rate in expectation, matching the convergence rate of SGD with variance reduction and RBCD.”
Coordinate Descent Converges Faster with the Gauss-Southwell Rule Than Random Selection (2015, methodology): “This strategy is popular for (cid:96) 1 -regularization [Shevade and Keerthi, 2003, Wu and Lange, 2008, Li and Osher, 2009] and in general is given by [see Bertsekas, 1999, § 8.4] However, the length of the step ( (cid:107) x k +1 − x k ) could be arbitrarily small under this choice.”
Learning Fast Approximations of Sparse Coding (2010, methodology): “The " backtracking " form of ISTA (not described here) automatically adjusts this constant as part of the algo- Algorithm 2 Coordinate Descent (Li & Osher, 2009) function CoD(X, Z, W d , S, α) Require: S = I − W T d W d Initialize: Z = 0; B = W T d X repeat ¯ Z = h α (B) k = index of largest…”
Reconstructing visual experiences from brain activity evoked by natural movies (2011, unknown): “L1-regularized linear regression [15, 16] was then used to fit a separate hemodynamic coupling term to each nonlinear filter (Figure 1; see also Supplemental Experimental Procedures available online).”