🔬 Compressed Sensing — MATLAB Implementations

MATLAB implementations of Compressed Sensing (CS) reconstruction algorithms for signals and images. Recover high-dimensional signals from far fewer measurements than the Nyquist rate using sparsity-exploiting techniques including L1 minimization, Orthogonal Matching Pursuit (OMP), and DCT-based compression.

---

✨ Features

• 📡 Signal Recovery — Reconstruct sinusoidal and speech signals from sub-Nyquist measurements
• 🖼️ Image Compression — FFT-based thresholding and JPEG compression analysis
• ⚙️ Multiple Solvers — CVX, l1magic, and MATLAB's built-in linprog (no external dependencies required)
• 📊 Performance Analysis — MSE, SNR, and measurement-vs-error tradeoff curves
• 🔊 Audio Playback — Listen to original vs reconstructed speech signals

---

📁 Project Structure

compressed-sensing-matlab/
├── signal/
│   ├── cs_signal_l1_cvx.m              # CS on sinusoidal signal via L1/CVX
│   └── cs_speech_reconstruction.m      # CS on speech signal — L1, CVX, linprog fallback
│
├── image/
│   ├── cs_image_fft_threshold.m        # Image CS via FFT2 coefficient thresholding
│   ├── image_jpeg_compression.m        # JPEG compression ratio analysis
│   └── cameraman100.jpg                # Test image
│
├── algorithms/
│   ├── cs_omp.m                        # Orthogonal Matching Pursuit (OMP) implementation
│   └── cs_static_reconstruction.m      # Static CS reconstruction framework
│
├── analysis/
│   └── time_frequency_domain.m         # Time & frequency domain analysis of audio + images
│
└── docs/
    └── Compressed_Sensing_Presentation.pptx

---

🚀 Getting Started

Prerequisites

• MATLAB R2020a or later
• Signal Processing Toolbox
• Optimization Toolbox (for linprog — included in base MATLAB)
• (Optional) CVX Toolbox — for convex optimization (download)

Note: The speech reconstruction script (cs_speech_reconstruction.m) automatically falls back to MATLAB's built-in linprog if CVX is not installed. No external dependencies are required.

How to Run

1. Clone this repository:

   git clone https://github.com/q-ms8/compressed-sensing-matlab.git

2. Open MATLAB and navigate to the project folder
3. Run any script:

   >> run('signal/cs_speech_reconstruction.m')

---

📡 Signal Recovery

Script	Description	Algorithm
cs_signal_l1_cvx.m	Recovers a 2-tone sinusoidal signal from M=300 random measurements (N=1000 samples)	L1 minimization via CVX
cs_speech_reconstruction.m	Reconstructs MATLAB's built-in speech signal from 30% of Nyquist samples	L1 / CVX / linprog (auto-fallback)

🖼️ Image Processing

Script	Description	Technique
cs_image_fft_threshold.m	Keeps only top 5% of FFT coefficients to reconstruct an image	FFT2 thresholding
image_jpeg_compression.m	Compares uncompressed vs JPEG images — file size, compression ratio, frequency domain	DCT-based compression (JPEG)

⚙️ Algorithms

Script	Description	Complexity
cs_omp.m	Orthogonal Matching Pursuit — greedy sparse recovery	O(K·M·N) per iteration
cs_static_reconstruction.m	Static reconstruction framework for CS experiments	Configurable

---

🧮 Mathematical Background

The Compressed Sensing Problem

Given a sparse signal x ∈ ℝᴺ with only K non-zero entries (K ≪ N), we acquire M linear measurements:

y = Φx     where Φ ∈ ℝᴹˣᴺ, M ≪ N

Recovery via L1 Minimization (Basis Pursuit)

minimize ‖s‖₁   subject to   Φψs = y

where ψ is the sparsifying basis (DCT, FFT, wavelet).

Key Conditions

• Sparsity: Signal must be sparse in some transform domain
• Incoherence: Measurement matrix Φ must be incoherent with sparsity basis ψ
• RIP: Restricted Isometry Property ensures stable recovery

Measurement Bound

For K-sparse signals in ℝᴺ, recovery requires approximately:

M ≥ C · K · log(N/K)

---

📊 Sample Outputs

• 📈 Original vs reconstructed signal comparison (time & frequency domain)
• 📉 Reconstruction error plots
• 🎼 Spectrogram comparison (original vs recovered speech)
• 🖼️ Image reconstruction from sparse coefficients
• 📊 Measurement count vs reconstruction error tradeoff curve

---

📝 License

This project is licensed under the MIT License — see the LICENSE file for details.