Sparse Frequency Estimation — Projection vs. LMMSE vs. LASSO vs. MUSIC

A Monte-Carlo study of four classical and modern estimators for recovering a handful of complex exponentials buried in noise. The headline result: when the frequency dictionary is overcomplete (N > P), ℓ₁ sparse recovery (LASSO) and subspace methods (MUSIC) decisively beat the classical projection / matched-filter and LMMSE receivers.

Course: ECEN 601 — Mathematical Methods in Signal Processing · Texas A&M University Author: Ishan Sharma

---

📡 The Problem

We observe a length-P complex signal that is a sum of k complex exponentials in additive complex Gaussian noise:

x[n] = Σ  s_i · e^{ j 2π f_i n }  +  z[n],     n = 0, 1, …, P−1
      i=1..k

Collecting the N candidate frequencies f_i on a uniform grid over [−½, ½), this becomes a linear model

x = A · s + z

• A — a P × N dictionary whose columns are the candidate complex exponentials
• s — an N × 1 k-sparse complex vector (only k of N entries are non-zero)
• z — circularly-symmetric complex Gaussian noise

The task: recover the support of s — i.e., which k of the N candidate frequencies are actually present — across a range of SNRs. Because k ≪ N and we do not know the frequencies in advance, this is a sparse recovery / line-spectrum estimation problem.

🧮 The Four Estimators

Estimator	Idea	File
Projection	Matched filter / periodogram: correlate x with every atom, keep the k strongest |aᵢᴴx|.	projection_estimator
LMMSE	Regularized linear MMSE estimate ŝ = s_p·Aᴴ(s_p·AAᴴ + σ²I)⁻¹x, rank by |ŝᵢ|.	lmmse_estimator
LASSO	ℓ₁-penalized sparse recovery (min ‖x−As‖² + λ‖s‖₁), complex handled via real/imag stacking.	lasso_estimator
MUSIC	Build a covariance matrix, split off the (M−k)-dim noise subspace, pick the k strongest pseudo-spectrum peaks.	music_estimator

A neat analytical insight: for this uniform DFT-style grid, the dictionary rows are orthogonal (A·Aᴴ = N·I). This makes the LMMSE estimate provably proportional to the matched-filter projection — so the two curves coincide exactly. The interesting gains come only from methods that exploit sparsity (LASSO) or subspace structure (MUSIC).

📊 Results

Detection error rate = average fraction of the k = 4 true frequencies missed (lower is better), over 1000 Monte-Carlo trials per SNR point.

Critically sampled — N = 32 = P

All four estimators behave well; the orthogonal dictionary means Projection and LMMSE are identical, with LASSO matching them and MUSIC trailing slightly.

Overcomplete — N = 48 > P = 32 ⭐ the interesting regime

SNR (dB)	Projection	LMMSE	LASSO	MUSIC
−4	0.338	0.338	0.280	0.354
0	0.268	0.268	0.141	0.205
4	0.254	0.254	0.072	0.121
8	0.258	0.258	0.037	0.065

When the dictionary is overcomplete, Projection and LMMSE plateau — extra SNR cannot overcome the basis leakage between non-orthogonal atoms. LASSO's ℓ₁ prior and MUSIC's subspace separation keep improving, with LASSO best throughout. This is the classic motivation for sparse recovery.

🗂️ The original course-submission results are preserved in results/original_simulation_results.png. See the note on reconstruction below.

▶️ Reproduce It

Python

cd python
pip install -r requirements.txt
python run_monte_carlo.py --trials 1000   # prints tables + writes CSVs
python plot_results.py                     # writes the figures in ../results

MATLAB

cd matlab
run_monte_carlo            % prints the Projection/LMMSE/LASSO/MUSIC tables

📂 Repository Structure

sparse-frequency-estimation/
├── python/                 # runnable NumPy / scikit-learn implementation
│   ├── signal_model.py     #   x = A s + z  data model
│   ├── estimators.py       #   projection · lmmse · lasso · music
│   ├── run_monte_carlo.py  #   SNR sweep → tables + CSV
│   └── plot_results.py     #   error-vs-SNR figures
├── matlab/                 # faithful MATLAB version (original language)
│   ├── create_*.m          #   data-generation helpers (per the project spec)
│   └── *_estimator.m       #   the four estimators + run_monte_carlo.m
├── results/                # generated figures, CSVs, and the original image
└── reference/              # third-party DOA MUSIC example (attributed, not mine)

⚙️ Note on Reconstruction

The original MATLAB project files were lost; this repository is a clean re-implementation built from the original project specification (signal model, parameters, and the four required estimators). It reproduces the project's central conclusions. Absolute error rates differ slightly from the archived results image because the original LASSO regularization value and random seed are not recoverable — the qualitative findings are identical.

🔬 Skills Demonstrated

• Statistical signal processing: spectral / line-frequency estimation, MUSIC & subspace methods, matched filtering, LMMSE estimation
• Sparse recovery / compressed sensing: ℓ₁ minimization (LASSO) for underdetermined systems, complex-valued formulation
• Rigorous evaluation: Monte-Carlo experiment design, SNR sweeps, support-recovery metrics
• Reproducible scientific computing: parallel MATLAB + Python implementations

📜 License

Code released under the MIT License. The reference/MUSIC.m file is © its original author (see reference/README.md).

---

Authored by Ishan Sharma · M.S. Electrical Engineering, Texas A&M University.