Related Experiment Video
Updated: May 15, 2026
13:44
Detection of Architectural Distortion in Prior Mammograms via Analysis of Oriented Patterns
Published on: August 30, 2013
Deterministic matrices matching the compressed sensing phase transitions of Gaussian random matrices
Hatef Monajemi1, Sina Jafarpour, Matan Gavish
1Department of Civil and Environmental Engineering, Stanford University, Stanford, CA 94305-4065, USA.
Summary
Compressed sensing recovery using convex optimization exhibits a predictable phase transition. This Gaussian phase transition accurately describes the performance of various deterministic matrices, not just random ones.
Area of Science:
- Signal Processing
- Applied Mathematics
- Information Theory
Background:
- Compressed sensing reconstructs signals from undersampled measurements.
- Recovery success depends on signal sparsity and measurement matrix properties.
- A phase transition governs recovery success for Gaussian random matrices.
Purpose of the Study:
- To investigate if the Gaussian phase transition applies to deterministic sensing matrices.
- To determine the universality of the phase transition in compressed sensing.
Main Methods:
- Conducted extensive experiments using various deterministic matrices (e.g., Spikes and Sines, Paley Frames).
- Analyzed the phase transition in the (k/n, n/N) phase diagram for k-sparse signals.
- Compared experimental results with the known phase transition for Gaussian random matrices.
Main Results:
- Deterministic matrices exhibit a phase transition for k-sparse signal recovery.
- The location of this phase transition coincides with that of Gaussian random matrices.
- This finding holds across different coefficient sets (e.g., binary, real, complex).
Conclusions:
- The Gaussian phase transition is a universal characteristic of compressed sensing recovery.
- Deterministic matrices behave similarly to random matrices regarding recovery performance.
- This universality simplifies the understanding and application of compressed sensing.
Related Concept Videos
01:30Gaussian Elimination: Problem Solving
Systems of linear equations in several variables are pivotal in modeling complex scenarios involving multiple unknowns and constraints. Such systems are widely used in various fields to represent relationships where several conditions must be simultaneously satisfied. Each variable in the system corresponds to an unknown quantity, while each equation imposes a linear constraint, leading to a structured approach for analyzing and solving real-world problems.A system of three equations with three...
01:23Linear time-invariant Systems
A system is linear if it displays the characteristics of homogeneity and additivity, together termed the superposition property. This principle is fundamental in all linear systems. Linear time-invariant (LTI) systems include systems with linear elements and constant parameters.
The input-output behavior of an LTI system can be fully defined by its response to an impulsive excitation at its input. Once this impulse response is known, the system's reaction to any other input can be calculated...
The input-output behavior of an LTI system can be fully defined by its response to an impulsive excitation at its input. Once this impulse response is known, the system's reaction to any other input can be calculated...
01:27Gauss's Law: Planar Symmetry
A planar symmetry of charge density is obtained when charges are uniformly spread over a large flat surface. In planar symmetry, all points in a plane parallel to the plane of charge are identical with respect to the charges. Suppose the plane of the charge distribution is the xy-plane, and the electric field at a space point P with coordinates (x, y, z) is to be determined. Since the charge density is the same at all (x, y) - coordinates in the z = 0 plane, by symmetry, the electric field at P...
01:10Computed Tomography
Tomography refers to imaging by sections. Computed tomography (CT) is a non-invasive imaging technique that uses computers to analyze several cross-sectional X-rays to reveal minute details about structures in the body.
The technique was invented in the 1970s and is based on the principle that as X-rays pass through the body, they are absorbed or reflected at different levels. In the technique, a patient lies on a motorized platform while a computerized axial tomography (CAT) scanner rotates...
The technique was invented in the 1970s and is based on the principle that as X-rays pass through the body, they are absorbed or reflected at different levels. In the technique, a patient lies on a motorized platform while a computerized axial tomography (CAT) scanner rotates...
00:59Propagation of Uncertainty from Random Error
An experiment often consists of more than a single step. In this case, measurements at each step give rise to uncertainty. Because the measurements occur in successive steps, the uncertainty in one step necessarily contributes to that in the subsequent step. As we perform statistical analysis on these types of experiments, we must learn to account for the propagation of uncertainty from one step to the next. The propagation of uncertainty depends on the type of arithmetic operation performed on...
01:15Sampling Theorem
In signal processing, the analysis of continuous-time signals, denoted as x(t), often involves sampling techniques to convert these signals into discrete-time signals. This process is essential for digital representation and manipulation. A critical component in sampling is the train of impulses, characterized by the sampling interval and the sampling frequency. The relationship between these parameters and the original signal's properties dictates the success of the sampling process.