Source-linked AI summary
On the reconstruction of block-sparse signals with an optimal number of measurements
Mihailo Stojnic, Farzad Parvaresh, Babak Hassibi
TL;DR
The paper asks whether block-sparse signals can be efficiently recovered from underdetermined random Gaussian measurements using near-optimal measurement counts. It analyzes a mixed ℓ2/ℓ1 relaxation and shows that, asymptotically, it recovers block-sparse signals up to roughly half the number of measurements under specified conditions, with polynomial-time solution via semidefinite programming.
Problem
Efficiently recovering the sparsest solution of an underdetermined system from random linear measurements remains a fundamental compressed-sensing question.
Method
The paper analyzes a mixed ℓ2/ℓ1 minimization for d-block-sparse signals and reduces the relaxation to a semidefinite program.
Results
As n tends to infinity, the method recovers any d-block-sparse signal with block sparsity βn, where β = 1/2 − O(ε), when α > 1 − 1/d and d = Ω(log(1/ε)/ε), with overwhelming probability.
Takeaways & Limitations
The ℓ2/ℓ1 algorithm reaches sparsity up to half the number of measurements with overwhelming probability, coinciding with the best achievable by exhaustive search.
Takeaways & Limitations
The probabilistic bound is loose for α less than one, and sharp thresholds for other α values are left for future work.
Abstract
from arXiv · showhide
Let A be an M by N matrix (M < N) which is an instance of a real random Gaussian ensemble. In compressed sensing we are interested in finding the sparsest solution to the system of equations A x = y for a given y. In general, whenever the sparsity of x is smaller than half the dimension of y then with overwhelming probability over A the sparsest solution is unique and can be found by an exhaustive search over x with an exponential time complexity for any y. The recent work of Candés, Donoho, and Tao shows that minimization of the L_1 norm of x subject to A x = y results in the sparsest solution provided the sparsity of x, say K, is smaller than a certain threshold for a given number of measurements. Specifically, if the dimension of y approaches the dimension of x, the sparsity of x should be K < 0.239 N. Here, we consider the case where x is d-block sparse, i.e., x consists of n = N / d blocks where each block is either a zero vector or a nonzero vector. Instead of L_1-norm relaxation, we consider the following relaxation min x \| X_1 \|_2 + \| X_2 \|_2 + ... + \| X_n \|_2, subject to A x = y where X_i = (x_{(i-1)d+1}, x_{(i-1)d+2}, ..., x_{i d}) for i = 1,2, ..., N. Our main result is that as n -> \infty, the minimization finds the sparsest solution to Ax = y, with overwhelming probability in A, for any x whose block sparsity is k/n < 1/2 - O(ε), provided M/N > 1 - 1/d, and d = Ω(\log(1/ε)/ε). The relaxation can be solved in polynomial time using semi-definite programming.
1. Introduction
The paper studies efficient recovery of block-sparse signals from underdetermined Gaussian measurements, replacing exhaustive search and standard ℓ1 relaxation with a mixed ℓ2/ℓ1 optimization. Its main theorem approaches the optimal half-measurement sparsity limit under sufficiently large block size.
- Problem: Compressed sensing seeks to recover a K-sparse N-dimensional signal from M≪N random linear measurements.The measurements are y=Ax, with A drawn from a real Gaussian ensemble.
- Prior approaches: The sparsest-solution formulation uses the ℓ0 norm but exhaustive reconstruction has exponential complexity.ℓ0 counts the nonzero elements of x.
- Proposed method: The paper models x as n blocks of size d and minimizes the sum of block ℓ2 norms subject to Ax=y.This mixed norm promotes solutions with few nonzero blocks rather than few nonzero coordinates.
- Main result: For d=Ω(log(1/ε)/ε), α>1−1/d, and β=1/2−O(ε), the relaxation efficiently recovers every d-block-sparse signal of block sparsity below βn with overwhelming probability.The result holds as n tends to infinity and the relaxation can be formulated as a semidefinite program.
- Analysis: The proof analyzes the measurement matrix's null space rather than restricted isometry or projected-polytope neighborliness.The authors note that their probabilistic union-bound estimate is loose when α<1.
2. Null-space characterization
The paper characterizes exact equivalence between block-sparse recovery and mixed-norm minimization through a null-space condition. It then studies that condition probabilistically for Gaussian measurement matrices.
- Equivalence proof: If the null-space inequality holds, any feasible perturbation increases the mixed norm, making the block-sparse solution unique.The converse constructs a competing feasible solution when the inequality fails.
- Null-space condition: Checking the k blocks with the largest ℓ2 norms is sufficient, although the theorem uses the condition for all subsets K.This simplification follows from ordering the block magnitudes.
- Null-space condition: The proof uses a null-space basis Z and partitions each vector w=Zv into n blocks W_i of size d.The resulting event is analyzed over all relevant block supports and coefficient vectors.
- Gaussian analysis: For Gaussian A, rotational invariance permits direct probabilistic analysis of the null space and supports the required high-probability bounds.The paper states that a null-space basis can be chosen with independent Gaussian entries.
3. Probabilistic analysis of the null-space characterization
The probabilistic analysis bounds failure of the block-sparse null-space condition for Gaussian matrices by covering the unit sphere and applying union bounds. Combining these estimates yields recovery thresholds approaching half the blocks when measurements nearly match unknowns.
- Null-space characterization: The proof analyzes an isotropically distributed Gaussian null-space rather than relying on restricted isometry or polytope neighborliness.The argument uses a generalized necessary-and-sufficient null-space condition for equivalence of the sparse and relaxed optimizations.
- Sphere covering: ε^-d(n−m) spheres of radius ε cover the unit sphere, reducing the continuous probability calculation to finitely many centers z_t.Each center satisfies ||z_t||_2 = 1 − ε^2, and the associated sets S_t are used to control nearby vectors.
- Finite reduction: The covering sets S_t are enclosed in polytopes P_t whose corner points permit bounding convex norm expressions by maxima over a finite collection.The reduction follows because a convex function on a polytope attains its maximum at a corner point.
- Failure probability: A union bound controls the probability that the null-space condition fails across block supports and covering points, although the resulting bound is loose for α below one.The authors expect sharper thresholds at other α values from an approach based on randomly projected simplices, generalized here to convex hulls of spheres.
- Threshold: For α > 1 − 1/d, d = Ω(log(1/ε)/ε), and β = 1/2 − O(ε), the relaxation recovers every d-block-sparse signal as n tends to infinity.The theorem assumes m = αn and block sparsity below βn, with overwhelming probability over the Gaussian matrix.
4. Numerical study of the block sparse reconstruction
The numerical study evaluates the ℓ2/ℓ1 recovery algorithm across block sizes and measurement ratios. The convex formulation is converted to a semidefinite program, with an additional support-selection modification used to improve practical reconstruction.
- Optimization: The block-sparse recovery problem minimizes the sum of block ℓ2 norms subject to Ax = y, forming a convex optimization problem.Each X_i contains the d coordinates in block i.
- Optimization: The convex formulation can be transformed into a semidefinite program solvable by numerical methods in polynomial time.This provides an efficient implementation of the mixed ℓ2/ℓ1 relaxation.
- Support refinement: The practical modification sorts reconstructed block norms and selects the k largest-norm blocks as the estimated support.The corresponding submatrix is then used to reconstruct the nonzero blocks, while the remaining blocks are set to zero.
- Experimental design: The experiments use block sizes d = 1, 4, 8, and 16, with N = 800 except N = 1600 for d = 16, and measurement ratios 0.1 ≤ α ≤ 0.9.For each setting, random Gaussian matrices and 100 signals at each sparsity level are tested.
- Evaluation: Success is measured as the percentage of trials achieving perfect recovery of the sparse signal.The reported curves summarize practical performance across sparsity and measurement settings.
5. Conclusion
The ℓ2/ℓ1 method efficiently recovers block-sparse signals under random Gaussian measurements, reaching half the measurement count near the square regime. The proof is loose at fixed measurement ratios, motivating sharper bounds.
- Conclusion: The ℓ2/ℓ1 algorithm can uniquely recover block-sparse signals up to half the number of measurements with overwhelming probability.This matches the best recovery level achievable by exhaustive search.
- Conclusion: The mixed ℓ2/ℓ1 minimization can be reduced to a semi-definite program.This provides an efficient computational formulation for the reconstruction problem.
- Conclusion: The proof appears to give a loose bound when the number of measurements is a fixed fraction of the number of unknowns.The paper identifies sharp recovery thresholds for ℓ2/ℓ1 as a direction for future work.
- Conclusion: Figure 2 plots the threshold for β at a given α using success probabilities from 100 independent d-block sparse signals.The experiments use a fixed Gaussian measurement matrix A, with curve colors indicating ℓ2/ℓ1 success probability.
A. Computing E
The derivation evaluates expectations involving norms of d-dimensional Gaussian vectors. It uses spherical-coordinate integrals, parabolic cylinder functions, their asymptotics, and large-d approximations.
- A. Computing E: The calculation begins by representing B1 as a d-dimensional vector with independent zero-mean Gaussian coordinates.Each coordinate has variance b^2 = 1 − ε^2 + c^2ε^2.
- A. Computing E: Spherical coordinates transform the relevant norm expectation into an integral involving the parabolic cylinder function U.The derivation then invokes asymptotic results for U when ζ ≫ 0 and t ≥ 0.
- A. Computing E: For d ≫ 0 and δ ≪ 1, the asymptotic expressions yield the desired approximation for the expectation.Here δ is treated as a constant independent of d.
B. Computing E
This derivation similarly evaluates a norm expectation for a d-dimensional Gaussian vector. It applies spherical coordinates and parabolic-cylinder-function asymptotics before obtaining a large-d approximation.
- B. Computing E: The calculation represents G1 as a d-dimensional vector with independent zero-mean Gaussian coordinates.The coordinate variance is specified in the surrounding derivation.
- B. Computing E: Spherical coordinates transform the norm integral into an expression involving the parabolic cylinder function U.The analysis again uses asymptotic results for U when ζ ≫ 0 and t ≥ 0.
- B. Computing E: For d ≫ 0 and δ ≪ 1, connecting the intermediate formulas produces the final approximation.The parameter δ is treated as a constant independent of d.