Veronese Compressed Sensing is $\exists \mathbb {R}$-Complete
IEEE Signal Processing Letters · 2026 · 33 · 2825-2828
DOI: 10.1109/lsp.2026.3710154 ↗Kurz gefasst
Fachartikel in der Zeitschrift IEEE Signal Processing Letters, 2026. Verfasst von Angshul Majumdar. Die Arbeit nennt 31 Literaturangaben.
Abstract (Originalsprache)
Sparse recovery is usually formulated over a finite dictionary, where the support is a subset of a finite index set. This letter studies an exact continuous analogue based on the degree- $D$ Veronese dictionary, whose atoms are indexed by points on the unit sphere and correspond to rank-one symmetric tensors. We define the decision problem Veronese-CS : given a rational coefficient vector and an integer $k$ , decide whether the vector admits a $k$ -term representation over the Veronese dictionary. We prove that Veronese-CS is complete for the existential theory of the reals $(\exists \mathbb {R})$ . Membership follows from a direct polynomial encoding of the unknown support locations and amplitudes. Hardness follows by a coefficient-preserving reduction from real Waring-rank feasibility, equivalently real symmetric tensor-rank feasibility. The novelty is to formulate this known algebraic hardness as an exact continuous compressed sensing statement over a fixed Veronese atom family. Thus exact sparse recovery over a canonical structured continuous dictionary already exhibits $\exists \mathbb {R}$ -complete complexity.
Zitieren
APA
Majumdar, A. (2026). Veronese Compressed Sensing is $\exists \mathbb {R}$-Complete. IEEE Signal Processing Letters, 33, 2825-2828. https://doi.org/10.1109/lsp.2026.3710154
Vancouver
Majumdar A. Veronese Compressed Sensing is $\exists \mathbb {R}$-Complete. IEEE Signal Processing Letters. 2026;33:2825-2828. doi:10.1109/lsp.2026.3710154
BibTeX
@article{Majumdar2026,
author = {Majumdar, Angshul},
title = {Veronese Compressed Sensing is $\exists \mathbb R$-Complete},
journal = {IEEE Signal Processing Letters},
year = {2026},
volume = {33},
pages = {2825--2828},
doi = {10.1109/lsp.2026.3710154}
}
EUVIMED