A Laplacian approach to _1-norm minimization
From MaRDI portal
Publication:2044482
Abstract: We propose a novel differentiable reformulation of the linearly-constrained minimization problem, also known as the basis pursuit problem. The reformulation is inspired by the Laplacian paradigm of network theory and leads to a new family of gradient-based methods for the solution of minimization problems. We analyze the iteration complexity of a natural solution approach to the reformulation, based on a multiplicative weights update scheme, as well as the iteration complexity of an accelerated gradient scheme. The results can be seen as bounds on the complexity of iteratively reweighted least squares (IRLS) type methods of basis pursuit.
Recommendations
- Iterative reweighted methods for \(\ell _1-\ell _p\) minimization
- Iterative reweighted minimization methods for \(l_p\) regularized unconstrained nonlinear programming
- A Globally Convergent Method for $l_p $ Problems
- scientific article; zbMATH DE number 62436
- A new spectral method for \(l_1\)-regularized minimization
Cites work
- scientific article; zbMATH DE number 1600999 (Why is no real title available?)
- scientific article; zbMATH DE number 3885116 (Why is no real title available?)
- scientific article; zbMATH DE number 3915531 (Why is no real title available?)
- scientific article; zbMATH DE number 1179517 (Why is no real title available?)
- scientific article; zbMATH DE number 2107836 (Why is no real title available?)
- scientific article; zbMATH DE number 6125590 (Why is no real title available?)
- A descent lemma beyond Lipschitz gradient continuity: first-order methods revisited and applications
- A mathematical introduction to compressive sensing
- A mathematical model for adaptive transport network in path finding by true slime mold
- An improved algorithm for basis pursuit problem and its applications
- Atomic decomposition by basis pursuit
- Bregman Iterative Algorithms for $\ell_1$-Minimization with Applications to Compressed Sensing
- Convergence of the linearized Bregman iteration for \(\ell _1\)-norm minimization
- Convex Analysis
- Electrical flows, Laplacian systems, and faster approximation of maximum flow in undirected graphs
- Evolutionary Games and Population Dynamics
- First-order methods in optimization
- For most large underdetermined systems of linear equations the minimal 𝓁1‐norm solution is also the sparsest solution
- Hessian Riemannian Gradient Flows in Convex Programming
- Iteratively reweighted least squares minimization for sparse recovery
- Linear models and generalizations. Least squares and alternatives. With contributions by Michael Schomaker.
- Matrix differential calculus with applications in statistics and econometrics
- Minimizing Effective Resistance of a Graph
- Mirror descent and nonlinear projected subgradient methods for convex optimization.
- Natural algorithms for flow problems
- On the convergence of alternating minimization for convex programming with applications to iteratively reweighted least squares and decomposition schemes
- On the convergence time of a natural dynamics for linear programming
- Optimization with sparsity-inducing penalties
- PhaseMax: Convex Phase Retrieval via Basis Pursuit
- Potential-function proofs for gradient methods
- Relatively smooth convex optimization by first-order methods, and applications
- Runtime guarantees for regression problems
- Smooth minimization of non-smooth functions
- The graphical lasso: new insights and alternatives
- The multiplicative weights update method: a meta-algorithm and applications
- Towards a stationary Monge-Kantorovich dynamics: the Physarum Polycephalum experience
- Two results on slime mold computations
- \textit{Physarum} can compute shortest paths
Cited in
(6)- When can \(l_p\)-norm objective functions be minimized via graph cuts?
- Physarum-inspired multi-commodity flow dynamics
- LPNN-based approach for LASSO problem via a sequence of regularized minimizations
- Revisiting the minimum-norm problem
- Fast iterative solution of the optimal transport problem on graphs
- A modified Bland's rule for solving \(l_1\) norm minimization
This page was built for publication: A Laplacian approach to \(\ell_1\)-norm minimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2044482)
