Homotopy Based Algorithms for \ell _{\scriptscriptstyle 0}-Regularized Least-Squares

DOI10.1109/TSP.2015.2421476MaRDI QIDQ4580645zbMATH OpenFDO

Authors Charles Soussen, J. Idier, Junbo Duan, David Brie

Publication date 22 August 2018

Published in IEEE Transactions on Signal Processing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1406.4802

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Abstract: Sparse signal restoration is usually formulated as the minimization of a quadratic cost function $|y-Ax{|}_2^2$, where A is a dictionary and x is an unknown sparse vector. It is well-known that imposing an $el{l}_0$ constraint leads to an NP-hard minimization problem. The convex relaxation approach has received considerable attention, where the $el{l}_0$-norm is replaced by the $el{l}_1$-norm. Among the many efficient $el{l}_1$ solvers, the homotopy algorithm minimizes $|y-Ax{|}_2^2+lambda|x{|}_1$ with respect to x for a continuum of $lambda$'s. It is inspired by the piecewise regularity of the $el{l}_1$-regularization path, also referred to as the homotopy path. In this paper, we address the minimization problem $|y-Ax{|}_2^2+lambda|x{|}_0$ for a continuum of $lambda$'s and propose two heuristic search algorithms for $el{l}_0$-homotopy. Continuation Single Best Replacement is a forward-backward greedy strategy extending the Single Best Replacement algorithm, previously proposed for $el{l}_0$-minimization at a given $lambda$. The adaptive search of the $lambda$-values is inspired by $el{l}_1$-homotopy. $el{l}_0$ Regularization Path Descent is a more complex algorithm exploiting the structural properties of the $el{l}_0$-regularization path, which is piecewise constant with respect to $lambda$. Both algorithms are empirically evaluated for difficult inverse problems involving ill-conditioned dictionaries. Finally, we show that they can be easily coupled with usual methods of model order selection.

Cited in

(14)

• Existence and convergence analysis of \(\ell_{0}\) and \(\ell_{2}\) regularizations for limited-angle CT reconstruction
• Weighted thresholding homotopy method for sparsity constrained optimization
• New insights on the optimality conditions of the \(\ell_2-\ell_0\) minimization problem
• Newton method for \(\ell_0\)-regularized optimization
• Constraint matrix factorization for space variant PSFs field restoration
• Global optimization for sparse solution of least squares problems
• A fast homotopy algorithm for gridless sparse recovery
• The sliding Frank-Wolfe algorithm and its application to super-resolution microscopy
• An homotopy method for l _p regression provably beyond self-concordance and in input-sparsity time
• A unified view of exact continuous penalties for _2-_0 minimization
• Comparing solution paths of sparse quadratic minimization with a Stieltjes matrix
• Co-cluster homotopy queuing model in nonlinear algebraic topological structure for improving poison distribution network communication
• Bayesian \(l_0\)-regularized least squares
• Pathwise optimization for bridge-type estimators and its applications

This page was built for publication: Homotopy Based Algorithms for $\ell _{\scriptscriptstyle 0}$-Regularized Least-Squares

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4580645)