EUVIMEDEUVIMED entdecken
Crossref

Veronese Compressed Sensing is $\exists \mathbb {R}$-Complete

Angshul Majumdar

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →