PreprintarXiv licencearXiv
Sparse Approximation via Polynomial Equations
Abstract
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.
Related
- A New Sparse Algorithm for Polynomial GCD over Integers
- The Moment Method for Computing Real Points of Sparse Polynomial Systems
- Subexponential Approximation of the Permanent in Deterministic Polynomial Time
- Approximation and composition of functions in quantized tensor trains via orthogonal polynomial expansions
- Dice enterprises and polynomial approximation: uniform query tails
BibTeX
@misc{tomic2026sparse,
title = {{Sparse Approximation via Polynomial Equations}},
author = {Matija Tomić and Raphaël Widdershoven and Lieven De Lathauwer},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.11215},
eprint = {2609.11215},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.11215},
}
RIS
TY - UNPB
TI - Sparse Approximation via Polynomial Equations
AU - Matija Tomić
AU - Raphaël Widdershoven
AU - Lieven De Lathauwer
PY - 2026
DA - 2026/09/10
PB - arXiv
DO - 10.48550/arxiv.2609.11215
UR - https://arxiv.org/abs/2609.11215
AB - 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.
ER -