Sublinear-time algorithms recover k-sparse signals under Jacobi polynomial orthogonal transforms by reducing to 1-sparse recovery under a sparsity structure assumption.
Improved Lower Bounds for the Restricted Isometry Property of Subsampled Fourier Matrices
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
Let $A$ be an $N \times N$ Fourier matrix over $\mathbb{F}_p^{\log{N}/\log{p}}$ for some prime $p$. We improve upon known lower bounds for the number of rows of $A$ that must be sampled so that the resulting matrix $M$ satisfies the restricted isometry property for $k$-sparse vectors. This property states that $\|Mv\|_2^2$ is approximately $\|v\|_2^2$ for all $k$-sparse vectors $v$. In particular, if $k = \Omega( \log^2{N})$, we show that $\Omega(k\log{k}\log{N}/\log{p})$ rows must be sampled to satisfy the restricted isometry property with constant probability.
fields
cs.DS 1years
2019 1verdicts
UNVERDICTED 1representative citing papers
citing papers explorer
-
Sparse Recovery for Orthogonal Polynomial Transforms
Sublinear-time algorithms recover k-sparse signals under Jacobi polynomial orthogonal transforms by reducing to 1-sparse recovery under a sparsity structure assumption.