How does basis pursuit differ from L2 minimization?

L2 minimization (least squares, min ||x||₂) distributes energy across all coefficients, producing non-sparse solutions. L1 minimization (basis pursuit, min ||x||₁) promotes sparsity by penalizing the number of non-zero coefficients. Geometrically, the L1 ball has sharp corners aligned with coordinate axes, so the intersection with the constraint hyperplane tends to occur at sparse points. For the underdetermined system Ax = y (fewer measurements than unknowns), L2 gives the minimum-norm solution (dense), while L1 gives the sparsest solution. This is the key insight of compressed sensing: if the signal is K-sparse in some basis, only O(K log(N/K)) measurements are needed instead of N.

What are the conditions for successful sparse recovery?

Basis pursuit succeeds when the sensing matrix A satisfies the Restricted Isometry Property (RIP): for all K-sparse vectors x, (1-δ)||x||₂² ≤ ||Ax||₂² ≤ (1+δ)||x||₂², where δ < √2 - 1 ≈ 0.414. Random Gaussian and sub-Gaussian matrices satisfy RIP with high probability when M ≥ O(K log(N/K)). For RF applications, random demodulation (mixing with pseudo-random sequences) and modulated wideband converter (MWC) architectures create measurement matrices that satisfy RIP. The number of measurements M needed for K-sparse recovery from N-dimensional signals: M ≈ 2K log(N/K) is typically sufficient.

Where is basis pursuit applied in RF?

Key RF applications include: 1) Wideband spectrum sensing: recover the spectrum occupancy map from sub-Nyquist samples, enabling cognitive radio to sense GHz-wide bands with MHz-rate ADCs. 2) Sparse DOA estimation: estimate directions of arrival with fewer antenna elements than conventional methods by exploiting angular sparsity. 3) Radar imaging: compressed sensing SAR reduces data acquisition time while maintaining image resolution. 4) Channel estimation: exploit sparse multipath structure in mmWave channels to estimate channel with fewer pilot symbols. 5) RFI mitigation: identify and remove sparse radio frequency interference from wideband observations.

Compressed Sensing

Basis Pursuit

Q: Where is basis pursuit applied in RF?

Key RF applications include: 1) Wideband spectrum sensing: recover the spectrum occupancy map from sub-Nyquist samples, enabling cognitive radio to sense GHz-wide bands with MHz-rate ADCs. 2) Sparse DOA estimation: estimate directions of arrival with fewer antenna elements than conventional methods by exploiting angular sparsity. 3) Radar imaging: compressed sensing SAR reduces data acquisition time while maintaining image resolution. 4) Channel estimation: exploit sparse multipath structure in mmWave channels to estimate channel with fewer pilot symbols. 5) RFI mitigation: identify and remove sparse radio frequency interference from wideband observations.

/BAY-sis pur-SOOT/

An optimization algorithm that recovers sparse signals by minimizing the L1 norm of the coefficient vector subject to measurement constraints: min ||x||₁ subject to Ax = y. Foundation of compressed sensing (Candès, Donoho, 2006). Enables sub-Nyquist sampling for wideband spectrum sensing, sparse DOA estimation, and compressed sensing radar. Requires only O(K log(N/K)) measurements for K-sparse signals in N dimensions.

Formulation: min ||x||₁ s.t. Ax = y

Measurements: O(K log N/K)

Guarantee: RIP (δ < √2−1)

Understanding Basis Pursuit

Conventional signal processing follows the Nyquist-Shannon theorem: to perfectly reconstruct a signal, you must sample at twice its bandwidth. For wideband RF signals spanning GHz, this requires extremely fast (and expensive) ADCs. Basis pursuit and compressed sensing break this requirement by exploiting signal sparsity: if a signal has only K significant components out of N possible, you need far fewer measurements than N.

The key insight is that L1 minimization promotes sparsity. While least squares (L2 minimization) spreads energy across all coefficients, the L1 norm's geometry (a diamond-shaped feasibility region) tends to find solutions where most coefficients are exactly zero. This mathematical property enables practical sub-Nyquist RF receivers that recover sparse spectra from far fewer samples than traditional approaches require.

Basis Pursuit Formulations

Basis Pursuit (noiseless):
min ||x||₁ subject to Ax = y

Basis Pursuit Denoising (BPDN):
min ||x||₁ subject to ||Ax − y||₂ ≤ ε

LASSO (equivalent):
min ||Ax − y||₂² + λ||x||₁

Recovery Guarantee (RIP):
M ≥ C × K × log(N/K) measurements
C ≅ 2 for Gaussian sensing matrices

Sparse Recovery Algorithms

Algorithm	Type	Complexity	Recovery Quality
Basis Pursuit (LP)	Convex optimization	O(N³)	Optimal
OMP	Greedy	O(KMN)	Good (fast)
CoSaMP	Greedy iterative	O(KMN)	Near-optimal
ISTA/FISTA	Proximal gradient	O(MN/iter)	Optimal (slow)
AMP	Message passing	O(MN/iter)	Optimal (fast)

Common Questions

Frequently Asked Questions

L1 vs. L2 minimization?

L2 (least squares): distributes energy, non-sparse. L1 (basis pursuit): promotes sparsity via diamond geometry. Underdetermined system: L2 = minimum-norm (dense), L1 = sparsest solution. Key compressed sensing insight.

Conditions for success?

Sensing matrix must satisfy RIP: δ < √2−1 ≅ 0.414. Random matrices satisfy with M ≥ 2K log(N/K). RF: random demodulation, modulated wideband converter (MWC) create valid sensing architectures.

RF applications?

Wideband spectrum sensing (cognitive radio). Sparse DOA estimation. Compressed SAR imaging. mmWave channel estimation (sparse multipath). RFI mitigation. All exploit signal sparsity for reduced sampling.

Related Terms

← Basis Function Batch Processing →

Compressed Sensing

Precision RF Components

RF Essentials provides precision terminations and custom waveguide assemblies for wideband receiver testing and sub-Nyquist sampling system characterization.

Request a Quote