Source-linked AI summary
Construction of a Large Class of Deterministic Sensing Matrices that Satisfy a Statistical Isometry Property
Robert Calderbank, Stephen Howard, Sina Jafarpour
TL;DR
Compressed sensing lacks a practical way to verify RIP for a given sensing matrix. This paper gives simple structural criteria for deterministic matrices, proving statistical near-isometry and mostly unique representations for random k-sparse signals, with lower-complexity reconstruction.
Problem
A practical algorithm is unavailable for efficiently verifying whether a sensing matrix satisfies RIP, which supports recovery guarantees for sparse signals.
Method
The paper imposes simple conditions including pointwise-multiplicative column groups, zero row sums, orthogonal rows, and bounded nonidentity column sums.
Results
The criteria guarantee successful recovery for all but an exponentially small fraction of k-sparse signals and apply to discrete chirp and Delsarte-Goethals matrices.
Takeaways & Limitations
The framework supports deterministic sensing matrices with expected reconstruction complexity quadratic in the number of measurements.
Abstract
from arXiv · showhide
Compressed Sensing aims to capture attributes of $k$-sparse signals using very few measurements. In the standard Compressed Sensing paradigm, the $\m\times \n$ measurement matrix $\A$ is required to act as a near isometry on the set of all $k$-sparse signals (Restricted Isometry Property or RIP). Although it is known that certain probabilistic processes generate $\m \times \n$ matrices that satisfy RIP with high probability, there is no practical algorithm for verifying whether a given sensing matrix $\A$ has this property, crucial for the feasibility of the standard recovery algorithms. In contrast this paper provides simple criteria that guarantee that a deterministic sensing matrix satisfying these criteria acts as a near isometry on an overwhelming majority of $k$-sparse signals; in particular, most such signals have a unique representation in the measurement domain. Probability still plays a critical role, but it enters the signal model rather than the construction of the sensing matrix. We require the columns of the sensing matrix to form a group under pointwise multiplication. The construction allows recovery methods for which the expected performance is sub-linear in $\n$, and only quadratic in $\m$; the focus on expected performance is more typical of mainstream signal processing than the worst-case analysis that prevails in standard Compressed Sensing. Our framework encompasses many families of deterministic sensing matrices, including those formed from discrete chirps, Delsarte-Goethals codes, and extended BCH codes.
I. INTRODUCTION AND NOTATIONS
The paper motivates deterministic compressed-sensing matrices whose expected guarantees apply to random k-sparse signals, avoiding practical RIP verification while preserving recovery relevance. It introduces statistical isometry and uniqueness conditions, simple design rules, and examples from coded constructions.
- Motivation: Compressed sensing reconstructs a k-sparse vector from N linear measurements using an N × C sensing matrix with k < N < C.The measurements are f = N^-1/2 Φα, with columns ϕj representing sensing vectors.
- Motivation: RIP is difficult to verify efficiently for a sampled sensing matrix, despite underpinning recovery guarantees for Basis Pursuit and Matching Pursuit.This motivates deterministic constructions with expected-case guarantees for random k-sparse signals.
- Definitions: Statistical RIP requires near-isometry inequalities to hold with probability exceeding 1 − δ for uniformly distributed k-sparse vectors of equal norm.The paper uses this weaker property because its analysis targets expected-case performance.
- Definitions: StRIP alone does not guarantee unique reconstruction with high probability, so the paper introduces UStRIP to require uniqueness for most k-sparse signals.The distinction concerns whether a randomly chosen signal has any distinct k-sparse signal with the same image.
- Contributions: The proposed framework offers easily checked deterministic criteria, lower-complexity recovery, and often storage-free matrix evaluation, contrasting with super-linear reconstruction in C.The criteria include group-based constructions and encompass linear-code approaches and expander-related deterministic matrices.
II. STRIP-ABLE: BASIC DEFINITIONS, WITH SEVERAL EXAMPLES
The paper defines StRIP-able matrices through simple structural conditions and derives consequences such as unimodular entries, tight frames, and distinct columns. Discrete chirp families provide a concrete example with efficient reconstruction and favorable spectral behavior.
- Basic conditions: An η-StRIP-able matrix satisfies three structural conditions that serve as sufficient design rules for statistical near-isometry.The stated conditions include orthogonal rows with zero row sums and columns forming a pointwise-multiplication group.
- Basic conditions: The column group contains an all-ones identity column, while the additional column-sum bound excludes that identity column.Columns are assumed nonrepeated and may be ordered so the identity is ϕ1.
- Immediate consequences: Pointwise group structure forces every matrix entry to have unit magnitude, and inverses provide closure under complex conjugation.These consequences support the algebraic analysis of the sensing matrix.
- Immediate consequences: The normalized columns form a tight frame with redundancy C/N when the relevant structural conditions hold.The frame relation follows from row orthogonality and the group-based conditions.
- Immediate consequences: Distinct columns have inner product magnitude below N unless they are identical, and the no-repeated-columns assumption therefore separates their labels.The argument uses Cauchy–Schwarz to characterize equality.
- Discrete chirp examples: For prime p, chirps use base frequency m and chirp rate r; an added phase factor makes their row sums vanish and satisfies the structural conditions.The resulting sensing matrix supports FFT-based recovery of chirp rate and base frequency.
- Discrete chirp examples: Experiments report deterministic chirp restriction singular values with a spread similar to Gaussian matrices and a central value closer to 1.The comparison uses the same N, C, and k values.
B. Kerdock, Delsarte-Goethals and Second Order Reed Muller Sensing Matrices
The paper constructs deterministic sensing matrices from code-based families and proves that simple structural conditions yield statistical near-isometry under explicit parameter constraints.
- Construction: The construction uses 2^m rows indexed by binary m-tuples and 2^(r+2)m columns indexed by Delsarte-Goethals matrix–vector pairs.The matrix entries are obtained by exponentiating codewords formed from x, P, and b over integers modulo 4.
- Proof strategy: The StRIP proof randomizes sparse-support indices through a permutation and controls concentration using a self-avoiding McDiarmid inequality for distinct-valued martingale differences.The sparse vector is generated by selecting a random permutation for its support and then random nonzero values.
- Caveat: A Cauchy-Schwarz step can weaken the bound when the nonzero coefficients differ substantially in magnitude.The paper notes that a more complicated bound is tighter for sparse vectors with entries of very unequal sizes.
- Guarantees: For ε > (k−1)/(C−1), the failure probability decreases to zero as C grows, and under η = 1 it approaches zero at rate C−1.The stated rate applies when k ≤ μ(C−1)ε + 1 for a constant μ < 1 and N = O(…).
B. Proving UStRIP: Uniqueness of Sparse Representation
The paper proves that suitable deterministic sensing matrices provide uniqueness of sparse representations for randomly selected sparse signals, extending statistical near-isometry guarantees. The proof combines incoherence, concentration, and subspace-dimension arguments under the condition η > 1/2.
- StRIP alone does not guarantee unique reconstruction, so the analysis bounds the probability that a random sparse signal has an “evil twin” with the same measurements.The competing signal must have a different support because near-isometry prevents collisions within the same support.
- For a support S containing two k-sparse signals, rank deficiency of the restricted Gram matrix Φ†Φ characterizes whether distinct representations can share measurements.The relevant union support has size at most 2k, although the proof later reduces the analysis to sets of cardinality at most k.
- η > 1/2 is sufficient for the concentration argument that gives a random set of k columns small coherence with every remaining column.The proof uses the Self-Avoiding McDiarmid inequality together with the structural condition on column sums, then applies a union bound over columns.
- Theorem 20 concludes that a randomly chosen k-sparse signal is the only k-sparse vector producing its measurement vector with probability at least 1−δ.For each well-conditioned support, possible collisions lie in a lower-dimensional, measure-zero subset under an absolutely continuous coefficient distribution.
IV. PARTIAL FOURIER ENSEMBLES
The paper analyzes partial Fourier matrices, where randomness enters through uniformly sampled rows, and shows that their column-average condition can be established with concentration bounds. This yields StRIP using only k log C measurements.
- Partial Fourier sensing matrices are formed by uniformly selecting N rows from the C × C discrete Fourier transform matrix.Their storage cost is O(N log C), compared with O(NC) for Gaussian and Bernoulli matrices.
- Uniform row sampling makes the expected entries of every non-identity Fourier column sum to zero, enabling concentration bounds for column averages.Hoeffding’s inequality is applied separately to the real and imaginary parts, followed by a union bound over columns.
- k log C measurements suffice for partial Fourier matrices to satisfy StRIP, improving the previous upper bound of k log5 C.The paper attributes this result to verifying condition (St3) with overwhelming probability and then applying Theorem 8.
V. QUADRATIC RECONSTRUCTION ALGORITHM
The Quadratic Reconstruction Algorithm exploits the algebraic structure of Delsarte-Goethals sensing matrices to recover sparse signals without matrix-vector multiplication. It identifies significant coefficients through Walsh-Hadamard peaks and reports near-information-theoretic measurement efficiency.
- The algorithm uses pointwise multiplication with shifted copies of the measurement vector, followed by a fast Walsh-Hadamard transform.At each iteration it finds a peak, estimates the corresponding coefficient, and updates the residual and recovered signal.
- The method avoids the matrix-vector multiplication required by Basis and Matching Pursuit on random matrices, giving reconstruction complexity sublinear in the data-domain dimension.Its operations use vector-vector multiplication in the measurement domain.
- Quadratic sensing structure separates sparse Walsh-Hadamard tones from uniformly distributed chirp-like cross terms, allowing iterative support and coefficient estimation.Varying the offset reveals terms in the sparse superposition, which can be peeled off by decreasing signal strength or processed in a list.
- Greater than 40-sparse superpositions were reconstructed numerically with deterministic Kerdock matrices having N = 2^9 and C = 2^18.The experiments are described as approaching the information-theoretic lower bound on the required number of measurements.
- Under the stated random-support, Gaussian-tail, and Gaussian-noise assumptions, StRIP bounds the algorithm’s approximation error relative to the best k-term approximation.The resulting error bound has an ℓ2/ℓ2 form and is reported as tighter than ℓ2/ℓ1 bounds for random ensembles and ℓ1/ℓ1 bounds for expander methods.
A. Noisy Measurements
The paper extends its deterministic sensing framework to measurements corrupted by independent Gaussian noise. It bounds the measured norm using the near-isometry parameter together with concentration of the noise norm.
- The noisy-measurement analysis assumes iid Gaussian noise that is uncorrelated with the measured signal.The paper introduces ε′ to simplify the proof while preserving the near-isometry interpretation of ε.
- Upper-tail deviations of the noisy measurement norm are bounded by controlling the sum of the noiseless near-isometric component and the Gaussian noise norm.The lower-tail estimate is handled similarly, and the final bound follows from union bounds.
B. Noisy Signals
The noisy-signal analysis considers reconstruction from measurements contaminated by white Gaussian noise and notes that the deterministic schemes alter the measurement-noise structure.
- White Gaussian source noise produces noisy measurements that the reconstruction algorithm must recover from.
- For independent noise samples across measurements, the paper reuses estimates from the preceding subsection.
- The measurement variance can be a factor C/N larger than the source-noise variance σ2.The passage describes this as a potentially huge factor and characterizes this noise as harder to handle.
VII. CONCLUSIONS
The paper gives simple criteria for deterministic sensing matrices that ensure successful recovery for nearly all k-sparse signals, and develops a code-structured reconstruction algorithm with quadratic measurement-domain complexity.
- VII. CONCLUSIONS: The criteria guarantee successful recovery of all but an exponentially small fraction of k-sparse signals.
- VII. CONCLUSIONS: They apply to deterministic families including subcodes of second-order binary Reed Muller codes and to random Fourier ensembles.For random Fourier ensembles, the criteria improve known measurement bounds for sparse reconstruction.
- VII. CONCLUSIONS: The proof of unique reconstruction uses a modified McDiarmid inequality for dependent variables.The paper identifies this inequality as potentially independently useful.
- VII. CONCLUSIONS: The Reed Muller reconstruction algorithm uses vector-vector multiplication in the measurement domain and has quadratic complexity in the number of measurements.This is contrasted with standard Basis and Matching Pursuit algorithms using matrix-vector multiplication and superlinear data-domain complexity.
APPENDIX A PROPERTIES OF DELSARTE-GOETHALS SENSING MATRICES
The appendix establishes algebraic and inner-product properties of Delsarte-Goethals sensing matrices, including closure of their columns under pointwise multiplication and a structured column construction.
- Group structure: The columns of the rth Delsarte-Goethals sensing matrix form a group under pointwise multiplication.
- Group structure: The group G has order 2(r+2)m when the binary symmetric matrix P ranges over the Delsarte-Goethals set.
- Inner products: Closure under pointwise multiplication reduces possible column inner products to column sums associated with Q = P ⊕ P′.
- Column sums: For a binary symmetric matrix Q of rank r, the appendix derives a column-sum expression involving 2^(m−r).The construction uses solutions to zQ = dQ, with the homogeneous solution space having dimension m−r.
- Matrix construction: The 0th Delsarte-Goethals matrix has N = 2m rows and N^2 columns arranged as N mutually unbiased bases.Vectors from one orthogonal basis appear noise-like to vectors from the other bases.
APPENDIX B GENERALIZED MCDIARMID’S INEQUALITY
The appendix generalizes McDiarmid’s inequality to distinct, dependent random variables by constructing martingale sequences and deriving concentration bounds from bounded differences.
- Motivation: The generalized result applies to distinct rather than independent random variables.The proof again proceeds by forming martingale sequences.
- Probability space: The probability space consists of tuples with pairwise distinct coordinates.
- Concentration result: The self-avoiding McDiarmid inequality bounds deviations of f from its expectation by 2 exp of a quantity determined by ε and the bounded differences.The theorem states the bound for every positive ε.
- Martingale construction: The martingale variables Z0 and Zm equal the expectation of f and the realized value f(X1, ..., Xm), respectively.Because the variables are restricted to distinct tuples, the Xℓ and Zℓ are not independent.
- Concentration proof: A bounded-difference condition controls each martingale increment by ci.The proof combines this bound with the martingale property and Hoeffding’s Lemma.