Exact and efficient basis pursuit denoising via differential inclusions and a selection principle
Gabriel P. Langlois, Jérôme Darbon · 2025
Read Exact and efficient basis pursuit denoising via differential inclusions and a selection principle by Gabriel P. Langlois, Jérôme Darbon (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-05562.txt.
Introduction
Gabriel P Langlois and Jérôme Darbon solve the lasso problem exactly with a new route through dynamical systems. The lasso is a workhorse method that fits data while forcing many weights to zero, picking out the few signals that matter. Standard solvers approach the answer step by step or follow a path of solutions. Their 2025 paper turns the dual problem into the path of a projected dynamical system. A selection principle from the theory of differential inclusions does the turning.
The team proves the system's path can be computed in full, giving the lasso answer up to machine precision. The same path yields the whole family of answers as the tuning knob varies. Speed is a bonus: the method is very fast in tests. Exact answers matter where audits or science demand no solver slack.
Catalog record
| CREATOR | Gabriel P. Langlois, Jérôme Darbon |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 166 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-05562
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Exact and efficient basis pursuit denoising via differential inclusions and a selection principle Gabriel P. Langlois, Jérôme Darbon Abstract Basis pursuit denoising (BPDN) is a cornerstone of compressive sensing, statistics and machine learning. While various algorithms for BPDN have been proposed, they invariably suffer from drawbacks and must either favor efficiency at the expense of accuracy or vice versa. As such, state-of-the-art algorithms remain ineffective for high-dimensional applications that require accurate solutions within a reasonable amount of computational time. In this work, we address this issue and propose an exact and efficient algorithm for BPDN using differential inclusions. Specifically, we prove that a selection principle from the theory of differential inclusions turns the dual problem of BPDN into calculating the trajectory of an integrable projected dynamical system, that is, whose trajectory and asymptotic limit can be computed exactly. Our analysis naturally yields an exact algorithm, numerically up to machine precision, that is amenable to computing regularization paths and very fast. Numerical experiments confirm that our algorithm outperforms the state-of-the-art algorithms in both accuracy and efficiency. Moreover, we show that the global continuation of solutions (in terms of the hyperparameter and data) of the projected dynamical system yields a rigorous homotopy algorithm for BPDN, as well as a novel greedy algorithm for computing feasible solutions to basis pursuit in strongly polynomial time. Beyond this work, we expect that our results and analysis can be adapted to compute exact or approximate solutions to a broader class of polyhedral-constrained optimization problems. Keywords: Basis pursuit denoising, Lasso, \ell_{1} -regularized least-squares, compressive sensing, statistics, machine learning, inverse problems, optimization, convex analysis, differential inclusions, projected dynamical systems, variational inequalities, exact solution, algorithms. Mathematics Subject Classification: 90C25, 65K05, 37N40, 46N10, 34A60, 62J07 1 Introduction Basis pursuit denoising (BPDN) is an important mathematical optimization problem relevant for high-dimensional applications in, e.g., compressive sensing, statistics, machine learning and inverse problems [ 17 , 61 , 48 , 69 , 58 ] . Also known as the lasso problem or the \ell_{1} -regularized least-squares problem, BPDN refers to the \ell_{1} -regularized least-squares problem \min_{\boldsymbol{x}\in\mathbb{R}^{n}}\left\{\left\|{\boldsymbol{x}}\right\|_{1}+\frac{1}{2t}\left\|{\bm{A}\boldsymbol{x}-\boldsymbol{b}}\right\|_{2}^{2}\right\}, (BPDN) where \bm{A} is a real m\times n matrix with m\leqslant n , \boldsymbol{b}\in\mathbb{R}^{m} is the observed data, and t\geqslant 0 is a hyperparameter controlling the trade-off between sparsity and data fidelity. The limit t\to 0 yields the basis pursuit (BP) problem \min_{\boldsymbol{x}\in\mathbb{R}^{n}}\left\|{\boldsymbol{x}}\right\|_{1}\quad\text{subject to}\quad\bm{A}\boldsymbol{x}=\boldsymbol{b}. (BP) The interpretation of \bm{A} and \boldsymbol{b} depends on the application, while the hyperparameter t is either preselected or estimated with data-driven methods such as cross-validation. Estimating the appropriate hyperparameter can prove challenging in practice. The standard approach is to construct a regularization path . To do so, one first selects a sequence \{t^{(k)}\}_{k=0}^{K} , one then computes the corresponding solutions \{\boldsymbol{x}^{s}(t^{(k)},\boldsymbol{b})\}_{k=0}^{K} to ( BPDN ), and one finally chooses the hyperparameter that gives the preferred solution. Different methods differ in how they select the hyperparameters and compute the solutions, but in any case, constructing a regularization path entails solving ( BPDN ) accurately for many hyperparameters. This approach can therefore become time-consuming and computationally intensive when the dimensions m and n are high. This issue has stimulated significant research to develop efficient and accurate algorithms for solving ( BPDN ) in high dimensions [ 50 , 49 , 25 , 18 , 29 , 22 , 6 , 16 , 11 ] . While many algorithms have been proposed for BPDN, they invariably suffer from drawbacks and must either favor efficiency at the expense of accuracy or vice versa. As such, the state-of-the-art algorithms remain ineffective for high-dimensional applications where accurate solutions are required in a reasonable amount of computational time. In this work, we address this issue and propose an exact and efficient algorithm for BPDN using differential inclusions. Our detailed analysis and results yield Algorithm 1 below. It computes an exact pair of primal and dual solutions to BPDN, numerically up to machine precision, is amenable to computing regularization paths, and is very fast. Input : A matrix \bm{A}\in\mathbb{R}^{m\times n} , a vector \boldsymbol{b}\in\mathrm{Im}({\bm{A}})\setminus{\{\boldsymbol{0}\}} and a number t\geqslant 0 . Output : A pair of primal and dual solutions (\boldsymbol{x}^{s}(t,\boldsymbol{b}),\boldsymbol{p}^{s}(t,\boldsymbol{b}))\in\mathbb{R}^{n}\times\mathbb{R}^{m} to basis pursuit denoising. Set \boldsymbol{p}^{(0)}\in\mathbb{R}^{m} such that \left\|{\bm{A}^{\top}\boldsymbol{p}^{(0)}}\right\|_{\infty}=1 ; 1 for k=1 until convergence do 2 Compute \mathcal{E}^{(k-1)}=\{j\in\{1,\dots,n\}:|\langle-\bm{A}^{\top}\boldsymbol{p}^{(k-1)},\boldsymbol{e}_{j}\rangle|=1\} ; 3 Compute \bm{D}^{(k-1)}=\mathrm{diag}\left(\mathrm{sgn}{(-\bm{A}^{\top}\boldsymbol{p}^{(k-1)})}\right) ; 4 Compute \hat{\boldsymbol{u}}^{(k-1)}\in\argmin_{\begin{subarray}{c}\boldsymbol{u}_{\mathcal{E}^{(k-1)}}\geqslant\boldsymbol{0}\\ \boldsymbol{u}_{{(\mathcal{E}^{(k-1)})^{\mathsf{C}}}}=\boldsymbol{0}\end{subarray}}\left\|{\bm{A}\bm{D}^{(k-1)}\boldsymbol{u}-\boldsymbol{b}-t\boldsymbol{p}^{(k-1)}}\right\|_{2}^{2} ; 5 Compute the descent direction \boldsymbol{d}^{(k-1)}=\bm{A}\bm{D}^{(k-1)}\hat{\boldsymbol{u}}^{(k-1)}-\boldsymbol{b}-t\boldsymbol{p}^{(k-1)} ; 6 Compute the maximal descent time \Delta^{(k-1)}=\min_{j\in\{1,\dots,n\}}\left\{\frac{\mathrm{sgn}{\left\langle\bm{D}^{(k-1)}\bm{A}^{\top}\boldsymbol{d}^{(k-1)},\boldsymbol{e}_{j}\right\rangle}-\left\langle\bm{D}^{(k-1)}\bm{A}^{\top}\boldsymbol{p}^{(k-1)},\boldsymbol{e}_{j}\right\rangle)}{\left\langle\bm{D}^{(k-1)}\bm{A}^{\top}\boldsymbol{d}^{(k-1)},\boldsymbol{e}_{j}\right\rangle}\right\}\; 7 if t>0 and t\Delta^{(k-1)}\geqslant 1 then 8 Set \boldsymbol{x}^{s}(t,\boldsymbol{b})=\bm{D}^{(k-1)}\hat{\boldsymbol{u}}^{(k-1)} ; Set \boldsymbol{p}^{s}(t,\boldsymbol{b})=\boldsymbol{p}^{(k-1)}+\boldsymbol{d}^{(k-1)}/t ; break; // The algorithm has converged else if t=0 and \boldsymbol{d}^{(k-1)}=\boldsymbol{0} then 9 Set \boldsymbol{x}^{s}(t,\boldsymbol{b})=\bm{D}^{(k-1)}\hat{\boldsymbol{u}}^{(k-1)} ; Set \boldsymbol{p}^{s}(t,\boldsymbol{b})=\boldsymbol{p}^{(k-1)} ; break; // The algorithm has converged Update \boldsymbol{p}^{(k)}=\boldsymbol{p}^{(k-1)}+\Delta^{(k-1)}\boldsymbol{d}^{(k-1)} ; 10 end for 11 Algorithm 1 Algorithm for computing a pair of primal and dual solutions (\boldsymbol{x}^{s}(t,\boldsymbol{b}),\boldsymbol{p}^{s}(t,\boldsymbol{b})) to basis pursuit denoising. Contributions of this paper: (i) In this work, we prove that a selection principle from the theory of differential inclusions turns the dual problem of BPDN into calculating the trajectory of an integrable projected dynamical system, that is, whose trajectory and asymptotic limit can be computed exactly. Our results and extensive analysis culminate in Algorithm 1, an active set algorithm that computes the optimal dual solution to BPDN and recovers an optimal primal solution exactly. As a by-product, our results provide a novel solution method for solving a broad class of projected dynamical systems, which should find relevance to applications outside BPDN. (ii) We present a detailed perturbation analysis of solutions to BPDN (in terms of the hyperparameter and data) via a global continuation argument of solutions of the projected dynamical system characterizing BPDN. This yields a rigorous generalized homotopy algorithm for BPDN, as well as a novel greedy algorithm for computing feasible solutions to basis pursuit in strongly polynomial time. (iii) Our numerical experiments show that Algorithm 1 vastly outperforms the state of the arts in accuracy while also achieving the best overall performance, highlighting a key feature of Algorithm 1: it neither compromises accuracy nor computational efficiency. Related work: The state-of-the-art algorithms for BPDN are divided roughly in three categories: coordinate descent methods [ 29 , 71 , 30 , 62 , 70 , 57 , 27 , 37 ] , first-order optimization algorithms such as FISTA or the PDHG algorithm [ 33 , 72 , 6 , 9 , 15 , 16 ] , and homotopy algorithms [ 50 , 49 , 25 , 22 , 63 , 11 ] . We will focus here only on these algorithms; a partial list of other algorithms include iteratively reweighted least squares algorithms [ 18 , 56 ] , approximate online algorithms [ 4 , 52 , 31 ] , Bayesian methods [ 34 , 36 , 51 , 42 , 1 ] , the adaptive inverse scale space method [ 14 ] , specialized Newton and quasi-Newton methods [ 73 , 40 , 66 ] , fixed-point continuation methods [ 35 ] , and interior point methods [ 10 ] . See [ 75 , 7 , 43 , 68 ] for surveys and comparisons of different methods and models. Coordinate descent methods are the state of the arts for high-dimensional BPDN because they are fast. Key to their efficiency are so-called selection rules or heuristics [ 62 , 32 ,