Sparse Recovery via $\ell_p^p/\ell_q^p$ Ratio Minimization: Theory and Algorithm
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916044556206080 |
|---|---|
| author | Yu, Lang Huang, Nan-jing |
| author_facet | Yu, Lang Huang, Nan-jing |
| contents | The constrained $\ell_p^p/\ell_q^p$ ratio model is scale invariant and is therefore attractive for sparse signal recovery. However, its nonconvex, nonsmooth, and fractional structure makes a unified theoretical and algorithmic analysis challenging for $0<p\le1$ and $q>1$. This paper develops a unified framework for this general model, covering deterministic exact recovery, stable recovery for sparse and compressible signals, and convergence analysis of a fractional algorithm. We first establish two deterministic sufficient conditions for exact recovery: a local optimality criterion and a null-space condition ensuring uniform recovery. For the $\ell_1/\ell_q$ subfamily, this null-space condition is further converted into high-probability sample-complexity bounds for isotropic sub-Gaussian matrix. We then study noisy recovery. Under the $k$-sparsity assumption, we improve the RIP-based stable recovery theory by relaxing the required sufficient condition and deriving sharper reconstruction-error bounds. For compressible signals, we establish RIP--ROP based error estimates whose constants are independent of the ambient dimension, improving prior bounds with explicit dimension-dependent factors [1]. An RIP-only variant is also derived. On the algorithmic side, we propose a prox-linear Dinkelbach framework that directly handles the fractional structure of the constrained problem and prove its convergence. Numerical experiments demonstrate that suitable choices of $(p,q)$ are effective for high-dynamic-range sparse signals and coherent sensing matrices. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_25397 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Sparse Recovery via $\ell_p^p/\ell_q^p$ Ratio Minimization: Theory and Algorithm Yu, Lang Huang, Nan-jing Optimization and Control The constrained $\ell_p^p/\ell_q^p$ ratio model is scale invariant and is therefore attractive for sparse signal recovery. However, its nonconvex, nonsmooth, and fractional structure makes a unified theoretical and algorithmic analysis challenging for $0<p\le1$ and $q>1$. This paper develops a unified framework for this general model, covering deterministic exact recovery, stable recovery for sparse and compressible signals, and convergence analysis of a fractional algorithm. We first establish two deterministic sufficient conditions for exact recovery: a local optimality criterion and a null-space condition ensuring uniform recovery. For the $\ell_1/\ell_q$ subfamily, this null-space condition is further converted into high-probability sample-complexity bounds for isotropic sub-Gaussian matrix. We then study noisy recovery. Under the $k$-sparsity assumption, we improve the RIP-based stable recovery theory by relaxing the required sufficient condition and deriving sharper reconstruction-error bounds. For compressible signals, we establish RIP--ROP based error estimates whose constants are independent of the ambient dimension, improving prior bounds with explicit dimension-dependent factors [1]. An RIP-only variant is also derived. On the algorithmic side, we propose a prox-linear Dinkelbach framework that directly handles the fractional structure of the constrained problem and prove its convergence. Numerical experiments demonstrate that suitable choices of $(p,q)$ are effective for high-dynamic-range sparse signals and coherent sensing matrices. |
| title | Sparse Recovery via $\ell_p^p/\ell_q^p$ Ratio Minimization: Theory and Algorithm |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2605.25397 |