An experimental comparison of modern solvers for solving the LP problem on test data generated according to theoretical recovery guarantees for matrices with normally distributed elements shows that the open-source solver Clarabel is a competitive alternative to proprietary solvers in terms of speed.
Abstract
In this work, we consider the problem of sparse signal recovery known as compressed sensing using $\ell_1$-minimization.
We show how the $\ell_1$-minimization problem (also known as basis pursuit) can be transformed into an equivalent linear programming (LP) problem, and provide a proof of the equivalence of these two problems.
We conduct an experimental comparison of modern solvers (Gurobi, HiGHS, CPLEX, and Clarabel) for solving the LP problem on test data generated according to theoretical recovery guarantees for matrices with normally distributed elements. The results show that the open-source solver Clarabel is a competitive alternative to proprietary solvers in terms of speed.
We also propose a method for verifying the uniqueness of the obtained solution using an auxiliary quadratic programming problem with a strictly convex objective function.
A geometric interpretation of the uniqueness conditions is provided, and the application of the method is demonstrated on an example of a matrix with integer elements.
Mathematical optimization plays a fundamental role in signal processing and wireless communications, serving as an essential framework for the systematic design of modern systems. Many design challenges in these fields, as well as in many others, can naturally be formulated as optimization problems. Over the years, the advancements in signal processing applications have significantly changed the structure and complexity of these optimization problems, creating new challenges in their analysis, understanding, and solution \cite{liu2024survey}. Consequently, the rapid development of sophisticated optimization theories and algorithms tailored to the demands of next-generation systems is crucial. Quadratic optimization problems constitute one of the most important classes of optimization problems in modern engineering systems. In signal processing and communications, quadratic forms naturally emerge when modeling power, energy, covariance matrices, and Euclidean distances, to name a few examples. Consequently, a broad family of practical design problems can be represented using quadratically constrained quadratic programs (QCQPs), where both the objective function and the constraints are quadratic functions of the optimization variables. While convex QCQPs can be solved efficiently using polynomial-time algorithms, the general non-convex QCQP remains computationally challenging. Specifically, indefinite quadratic forms and rank constraints often induce NP-hardness. Non-convex QCQP problems arise in a broad range of signal processing, communications, control, machine learning, and network optimization applications.
In this paper, we develop and analyze techniques for recovering a linear image $Bx$ of an unknown signal $x$ from indirect noisy observation $\omega=Ax+\xi$. It is {\em a priori} known that $x\in \cX$, a given convex compact set, and that $x$ is $s$-sparse---has at most $s$ nonvanishing entries. The proposed estimates belong to a large family of recovery routines by $\ell_1$-minimization. However, unlike the classical result describing performance of such estimates, we do not make any special (and hard to check) assumptions about the sensing matrix $A$ such as nullspace or Restricted Isometry condition and the like. As a consequence, parameters of the estimates and the upper bounds on their risks are not available in a closed analytic form, but are delivered instead by efficient computation as solutions to explicit convex optimization problems.
Classical sampling theory fixes the rate at which a signal must be measured by its bandwidth alone. Compressed sensing replaces that criterion with one based on structure: a signal that is sparse in some known basis can be reconstructed exactly from a number of linear measurements proportional to its sparsity and only logarithmic in its ambient dimension. This paper reviews the conditions under which such recovery is possible, the algorithms that achieve it, and the settings in which the theory has been applied. Uniqueness requires that the measurement matrix act almost isometrically on sparse vectors, a property that random matrices possess with high probability but that is difficult to certify for any given matrix. Under that property the combinatorial search for the sparsest solution can be replaced by minimisation of the sum of absolute values, a convex program, and the reconstruction is stable when measurements are noisy and the signal is only approximately sparse. Two numerical experiments carried out for this review illustrate the sharp boundary between success and failure as sparsity and the number of measurements are varied. Applications in magnetic resonance imaging and radio astronomy are examined together with the limits of the approach.
S. E· International Journal of Pur...· 0 citations
We discuss some theoretical results and their applications to specific practical problems from wireless communications. We assume that we know the noisy version of the signal, which is sparse with respect to a given system of elements (dictionary), at a finite number of points and we want to approximately recover it. This problem of recovery of a noisy signal is closely related to the problem of establishing the Lebesgue-type inequalities for the corresponding algorithms and it motivates us to prove such inequalities. Under certain conditions on a dictionary (RIP-type condition, coherence condition) we obtain different kinds of the Lebesgue-type inequalities for the OMP and its version WOMP algorithms. The most important feature of our new theoretical result is the assumption that the dictionary has the RIP-type property instead of the assumption that it is the Riesz basis, which was used in the previous results. Our approach allows us to treat redundant (overcomplete) systems, which is important in applications. We consider the setting of sparse recovery for highly-coherent dictionaries that appear in OFDM setting for wireless communication. Our main example is the oversampled Fourier dictionary and the recovery of the frequency response of a sparse channel. We develop a general approach to such problems and we prove that under certain conditions the OMP algorithm recovers all dictionary elements with large coefficients, and estimate its accuracy (in NMSE metric) in terms of signal-to-noise ratio.
M. Makurin, Y. Malykhin, K. Ryutin et al.· 0 citations
We consider the problem of finding sparse solutions of an underdetermined linear system $Ax=b$. In contrast to conventional approaches based on greedy algorithms or convex relaxation, we reformulate sparse approximation as a structured system of polynomial equations and connect with the literature on tensor methods. We develop an eigenvalue decomposition based method that formally guarantees recovery of all sparse solutions if there is more than one. We also develop two optimization-based methods achieving favorable computational complexity. The new methods allow explicit control of the target sparsity. Numerical experiments illustrate the performance and compare to basis pursuit (denoising) and orthogonal matching pursuit.
Matija Tomić, Raphaël Widdershoven, L. De Lathauwer· 0 citations
We study sparse image recovery under the non-convex ℓp/ℓq ratio regularisation, a generalisation of the classical ℓ1/ℓ2 ratio. The problem is non-convex and non-smooth, and arises in compressed-sensing image reconstruction and sparse-representation-based classification. A genuine Gauss–Seidel coordinate-descent solver is proposed, which operates on signed variables, introduces no auxiliary variable, and requires only a single hyper-parameter. A small positive offset is added to the denominator to keep the ratio well-defined at the origin. At every coordinate update the residual gradient and the denominator weight are refreshed on-line, reducing the per-coordinate sub-problem to a standard $\ell _p^p$ prox that admits a closed form for the canonical low values of p and a smoothed inverse-power IRL1 update for any other p. A convergence guarantee is established for the surrogate iterates, and a separate remark addresses the surrogate-consistency gap to the original ratio problem. Across three experimental phases the six GS-ℓp/ℓq variants match or exceed the strongest baseline on all five classification datasets, gain +1.5dB over the ℓ1/ℓ2 ADMM baseline on BSD68 denoising, and run one to two orders of magnitude faster per reconstruction. Code and data are released with the paper.
Zi-He Zheng· 2026 3rd International Confe...· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
