Source-linked AI summary
The Computational Complexity of the Restricted Isometry Property, the Nullspace Property, and Related Concepts in Compressed Sensing
Andreas M. Tillmann, Marc E. Pfetsch
TL;DR
The paper asks whether computationally useful sparse-recovery conditions can be evaluated efficiently despite the underlying sparsest-solution problem being NP-hard. It reduces these questions to matrix spark complexity and proves NP-hardness for computing RIP and NSP constants, along with related complexity results.
Problem
Finding sparsest solutions is NP-hard, while the computational complexity of evaluating RIP and NSP constants had lacked general rigorous proofs.
Method
The paper proves spark computation hardness through a reduction from k-Clique and reduces RIP and NSP constant problems to small linearly dependent column subsets.
Results
Computing the restricted isometry constant and nullspace constant is NP-hard, and certifying the RIP is also NP-hard.
Takeaways & Limitations
RIP and NSP provide useful sparse-recovery guarantees, but their optimal constants are computationally intractable to determine in general.
Abstract
from arXiv · showhide
This paper deals with the computational complexity of conditions which guarantee that the NP-hard problem of finding the sparsest solution to an underdetermined linear system can be solved by efficient algorithms. In the literature, several such conditions have been introduced. The most well-known ones are the mutual coherence, the restricted isometry property (RIP), and the nullspace property (NSP). While evaluating the mutual coherence of a given matrix is easy, it has been suspected for some time that evaluating RIP and NSP is computationally intractable in general. We confirm these conjectures by showing that for a given matrix A and positive integer k, computing the best constants for which the RIP or NSP hold is, in general, NP-hard. These results are based on the fact that determining the spark of a matrix is NP-hard, which is also established in this paper. Furthermore, we also give several complexity statements about problems related to the above concepts.
I. INTRODUCTION
The paper studies computational conditions for recovering sparsest solutions efficiently, focusing on the complexity of RIP and NSP constants and their connection to spark.
- I. INTRODUCTION: Finding a sparsest solution to an underdetermined linear system is NP-hard, motivating efficient recovery methods such as ℓ1-minimization.Basis pursuit replaces the ℓ0 objective with an ℓ1 objective under suitable recovery conditions.
- I. INTRODUCTION: Evaluating the best RIP and NSP constants was conjectured to be computationally hard, although rigorous NP-hardness proofs had generally been absent.Existing work included approximation methods, semidefinite relaxations, and partial hardness results under non-standard assumptions.
- I. INTRODUCTION: The paper proves that computing the restricted isometry constant and nullspace constant for a given matrix and order k is NP-hard.The results establish that no polynomial-time algorithm computes δ_k for all instances unless P=NP.
- I. INTRODUCTION: The proofs establish spark computation as NP-hard and reduce the RIP and NSP complexity results to small linearly dependent column subsets.The spark proof adapts a reduction from k-Clique to vector matroids; the paper also derives further strong NP-hardness results for related problems.
II. COMPLEXITY ISSUES RELATED TO THE SPARK
This section establishes NP-completeness and NP-hardness results for detecting small circuits and computing the spark of a rational matrix. The proof reduces k-Clique to circuit existence using an explicit matrix construction, yielding further hardness results for circuit-constrained and full-spark problems.
- Definitions: A circuit is an inclusionwise minimal linearly dependent set of columns, and the spark is the size of the smallest circuit.The incidence-matrix rank lemmas support the reduction’s analysis of circuits.
- Technical distinction: Circuit size and nullspace-vector support are distinct: spark(A) ≤ k does not generally imply a nullspace vector with exactly k nonzeros.This distinction is used in the subsequent proofs.
- Main hardness result: The problem of deciding whether a rational matrix has a circuit of size at most k is NP-complete.Membership in NP follows because circuit size and the required rank conditions can be verified by Gaussian elimination.
- Reduction: The reduction from k-Clique constructs an explicit matrix whose circuit of the target size exists if and only if the graph contains a k-clique.The construction combines a vertex-edge incidence matrix with a Vandermonde block and has polynomial encoding length.
- Consequences: Computing spark(A) is NP-hard, and deciding whether a circuit has exactly a specified size is also NP-complete.The explicit construction avoids relying on unspecified generic matrices or transversal-matroid representations.
- Related complexity results: Finding a minimum circuit containing a specified column is strongly NP-hard, while deciding whether a rational matrix is full spark is coNP-complete.The column-constrained result is strongly NP-complete in its decision form.
III. NP-HARDNESS OF COMPUTING THE RESTRICTED ISOMETRY CONSTANT
This section studies the complexity of the restricted isometry constant and RIP certification. It reduces these questions to small circuits, using matrix scaling to control the upper RIP inequality and expose the lower inequality.
- Definitions: The restricted isometry constant δ_k is the smallest constant for which the RIP inequalities hold for every vector with at most k nonzero entries.The paper also uses the equivalent global upper-bound form after scaling.
- Certification: RIP certification for a given δ_k in (0, 1) is NP-hard, so no polynomial-time algorithm solves these problems for all instances unless P=NP.The paper states this alongside NP-hardness of RIC computation and coNP-completeness of the δ_k < 1 decision problem.
- Reduction mechanism: Scaling a matrix preserves its column dependencies while making the upper RIP inequality automatically valid, so complexity is determined by the lower inequality.The scaling factor has polynomial encoding length, and singular-value interlacing controls every submatrix’s largest singular value.
- RIP decision problem: Deciding whether some rational δ_k < 1 makes a given matrix satisfy the RIP of order k is coNP-complete.The no certificate is a sparse rational nullspace vector, while hardness follows by reduction from small-circuit existence.
- Hardness of RIC computation: Computing the RIC δ_k for a rational matrix and positive integer k is NP-hard.This follows from the NP-completeness of deciding whether a circuit of size at most k exists.
A. RIP certification
RIP certification is computationally hard: deciding whether a matrix satisfies RIP for a specified order and constant is NP-hard. The proof connects this problem to spark, using a polynomially bounded separation when no small circuit exists.
- If spark(A) > k, a polynomially encoded ε > 0 lower-bounds ∥Ax∥₂² by ε∥x∥₂² for every k-sparse x.The encoding length of ε is polynomially bounded by the encoding length of A.
- RIP certification—deciding whether A satisfies RIP of order k with given δ_k ∈(0, 1)—is NP-hard.
- A circuit of size at most k makes RIP impossible for any δ_k ∈(0, 1), because a nonzero k-sparse vector lies in the nullspace.
- The hardness reduction distinguishes matrices with small circuits from matrices whose sparse vectors satisfy a positive lower bound, yielding the certification result.
B. Asymmetric restricted isometry constants
The paper establishes strong hardness results for asymmetric and symmetric restricted isometry constants, linking sparse spectral optimization and graph cliques to RIC computation. It also proves strong NP-hardness for Sparse PCA and notes open containment questions.
- Upper asymmetric RIC: It is NP-hard in the strong sense to decide whether the upper asymmetric RIC δ^U_k is below a parameter δ, even for square matrices.Consequently, computing δ^U_k is strongly NP-hard.
- Sparse PCA: Sparse PCA is strongly NP-hard because its sparse quadratic optimization can distinguish graphs containing a k-clique from those without one.The reduction uses adjacency matrices and polynomially bounded numerical values.
- Upper asymmetric RIC: The upper asymmetric RIC reduction encodes k-cliques through the largest eigenvalues of k × k principal submatrices.A k-clique corresponds to a submatrix with largest eigenvalue n² + k − 1.
- RIC computation: The paper proves that computing the RIC δ_k is NP-hard in the strong sense, including in the square case m = n.
IV. NP-HARDNESS OF COMPUTING THE NULLSPACE CONSTANT
The paper establishes hardness results for the nullspace constant by reducing NSP questions to the existence of small linearly dependent column subsets, characterized through matrix circuits.
- NSP hardness: The nullspace constant α_k is the smallest value for which the NSP inequality holds for every vector in the nullspace of A.It can equivalently be expressed through a maximization over supports of size at most k and normalized nullspace vectors.
- NSP hardness: The NSP of order k asks whether a matrix satisfies the nullspace inequality with some constant α_k < 1, and this decision problem is coNP-complete.The result concerns rational matrices A and positive integers k.
- Complexity classification: The NSP “no” answer has a polynomially checkable certificate consisting of a rational nullspace vector and a support set of size at most k.The certificate vector can be chosen with polynomially bounded encoding length.
V. CONCLUDING REMARKS
The concluding remarks delimit the hardness results, motivate approximation and heuristic approaches, and identify open questions about approximation and stronger hardness for related constants.
- Scope of hardness results: The results establish coNP-completeness for testing whether RIP or NSP holds with some constant below 1, but not for every fixed constant below 1.When k is fixed, the corresponding questions become solvable in time O(n^poly(k)).
- Scope of hardness results: The RIP hardness construction uses δ_k values very close to 1, far from values that could yield recovery guarantees.The NSP result similarly proves hardness for deciding whether α_k < 1, while recovery guarantees require α_k < 1/2.
- Algorithmic implications: Because exact polynomial-time computation is hard, the authors justify investigating general approximation algorithms that compute bounds on the RIP constants.The conclusion points to approximation work rather than searching only for exact polynomial-time algorithms.
- Algorithmic implications: Mutual coherence is efficiently computable and can bound the RIC, NSC, and spark, but its recovery guarantees often apply only at practically small sparsity levels.This limitation motivates studying RIP, NSP, and spark despite their computational intractability.
- Open problems: Future work includes determining approximation hardness for RIP and NSP constants and whether spark and NSC computations are strongly NP-hard.Existing inapproximability results for RIP rely on less common complexity assumptions.
- Open problems: CoNP-hardness does not rule out practically efficient algorithms, and prior work sometimes improves on exhaustive RIP certification using monotonicity or sandwiching procedures.These approaches exploit structural properties of the constants rather than eliminating worst-case hardness.
- Algorithmic implications: No pseudo-polynomial algorithm can compute the RIC in general unless P=NP.The conclusion notes that more exact-algorithm research could clarify RIP and NSP behavior.