Computational complexity of certifying restricted isometry property

DOI10.4230/LIPICS.APPROX-RANDOM.2014.371MaRDI QIDQ2969632zbMATH OpenOpenAlexFDO

Authors A. Natarajan, Yi Wu

Publication date 22 March 2017

Full work available at URL https://arxiv.org/abs/1406.5791

zbMATH Keywords

restricted isometry propertyRIP certificationsparse Cheeger inequalitySSE-hardness

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Norms of matrices, numerical range, applications of functional analysis to matrix theory (15A60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Abstract: Given a matrix $A$ with $n$ rows, a number $k<n$, and $0<delta<1$, $A$ is $(k,delta)$-RIP (Restricted Isometry Property) if, for any vector $xinmathbb{R}^n$, with at most $k$ non-zero co-ordinates, ${\displaystyle }$(1-delta) |x|_2 leq |A x|_2 leq (1+delta)|x|_2${\displaystyle }$ In many applications, such as compressed sensing and sparse recovery, it is desirable to construct RIP matrices with a large $k$ and a small $delta$. Given the efficacy of random constructions in generating useful RIP matrices, the problem of certifying the RIP parameters of a matrix has become important. In this paper, we prove that it is hard to approximate the RIP parameters of a matrix assuming the Small-Set-Expansion-Hypothesis. Specifically, we prove that for any arbitrarily large constant $C>0$ and any arbitrarily small constant $0<delta<1$, there exists some $k$ such that given a matrix $M$, it is SSE-Hard to distinguish the following two cases: - (Highly RIP) $M$ is $(k,delta)$-RIP. - (Far away from RIP) $M$ is not $(k/C,1-delta)$-RIP. Most of the previous results on the topic of hardness of RIP certification only hold for certification when $delta=o(1)$. In practice, it is of interest to understand the complexity of certifying a matrix with $delta$ being close to $sqrt2-1$, as it suffices for many real applications to have matrices with $delta=sqrt2-1$. Our hardness result holds for any constant $delta$. Specifically, our result proves that even if $delta$ is indeed very small, i.e. the matrix is in fact emph{strongly RIP}, certifying that the matrix exhibits emph{weak RIP} itself is SSE-Hard. In order to prove the hardness result, we prove a variant of the Cheeger's Inequality for sparse vectors.

Recommendations

• Restricted isometry property for general p-norms
• Explicit Construction of RIP Matrices Is Ramsey‐Hard
• Explicit constructions of RIP matrices and related problems
• An Improved Estimate in the Restricted Isometry Problem
• On model-based RIP-1 matrices

Cited in

(2)

• Effective zero-norm minimization algorithms for noisy compressed sensing
• Certifying the Restricted Isometry Property is Hard

This page was built for publication: Computational complexity of certifying restricted isometry property

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2969632)