📊 statistics

Denoising data using convex relaxations

This paper proposes a convex-relaxation denoising estimator that projects noisy observations onto the convex hull of a low-dimensional latent manifold, providing finite-sample error guarantees under specific distributional conditions and validating the framework for Cryo-Electron Microscopy applications.

Original authors: Charles Fefferman, Aalok Gangopadhyay, Matti Lassas, Jonathan Marty, Hariharan Narayanan

Published 2026-05-05

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Charles Fefferman, Aalok Gangopadhyay, Matti Lassas, Jonathan Marty, Hariharan Narayanan

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to reconstruct a beautiful, intricate sculpture that is hidden inside a thick, swirling fog. You can't see the sculpture directly; you can only see thousands of blurry, distorted snapshots of it. Some snapshots are taken from the front, some from the side, and every single one is covered in static (noise).

This paper presents a clever, mathematically rigorous way to clean up those blurry snapshots and recover the shape of the original sculpture. Here is how the authors, led by Charles Fefferman and colleagues, explain their method using simple concepts.

The Core Problem: The "Foggy" Data

In many scientific fields (like medical imaging or astronomy), we collect high-dimensional data (data with many numbers describing a single point). The authors assume that this data isn't random chaos; it actually lies on a hidden, low-dimensional "shape" or manifold.

Think of the manifold as a thin, crumpled piece of paper floating in a huge 3D room. Even though the room is 3D, the paper is only 2D.

The Clean Data ( $X$ ): Points lying perfectly on that crumpled paper.
The Noise ( $Z$ ): Random static (like snow on an old TV) added to every point.
The Observed Data ( $Y$ ): The messy points you actually see ( $Y = X + Z$ ).

The goal is to take the messy points ( $Y$ ) and push them back onto the clean paper ( $X$ ).

The Solution: A Three-Step "Denoising" Machine

The authors propose an algorithm that works in three main stages, which they prove mathematically will work well even with a limited number of samples.

1. Finding the Right Room (Dimensionality Reduction)

First, the algorithm looks at the messy data to figure out which direction the "crumpled paper" is mostly facing.

The Analogy: Imagine the paper is floating in a 100-dimensional room, but it's mostly flat in just 5 directions. The algorithm uses a technique called Principal Component Analysis (PCA) to ignore the 95 directions where there is mostly just noise and focus on the 5 directions where the real shape lives.
The Result: It projects all the messy data into this smaller, cleaner "room" (a lower-dimensional space). This gets rid of a huge chunk of the noise immediately.

2. Building a Safety Net (The Convex Hull)

Once the data is in the smaller room, the algorithm needs to know where the "paper" is. But here's the trick: they don't try to trace the exact crumpled paper. Instead, they build a convex hull.

The Analogy: Imagine stretching a rubber band around the outer edges of the crumpled paper. The shape inside the rubber band is the "convex hull." It's a solid, smooth shape that contains the paper.
Why do this? It's much easier to mathematically "snap" a point to the surface of a smooth, solid shape (like a rubber band) than to a crumpled, jagged piece of paper. The algorithm projects the noisy points onto this rubber band.

3. The "Distance Oracle" (The Magic Ruler)

This is the most innovative part. To project the points onto the rubber band, the algorithm needs to know exactly how far the rubber band is from any given line. But since the rubber band is made of noisy data, they don't know its exact shape.

The Analogy: Imagine you are in a dark room trying to find the edge of a table. You can't see the table, but you can throw darts at the wall. If you throw enough darts, you can count how many land past a certain line. If very few darts land past a line, that line is probably far away from the table. If many land past it, the line is close.
The Method: The authors built a statistical "ruler" (an oracle) that looks at the distribution of the noisy points. By counting how many points fall into the "tails" of the noise distribution (the extreme outliers), they can estimate the distance to the hidden shape with high precision. They use this ruler to guide the projection.

Why It Works (The Guarantees)

The paper doesn't just say "this looks like it works." They provide a mathematical guarantee.

They prove that if you have enough data points, the error (the distance between your cleaned-up point and the true original point) will be small.
They break the error down into three parts:
1. The PCA Error: How much the "room" they chose differs from the true shape.
2. The Statistical Error: The natural fuzziness of projecting onto a rubber band when you have noise.
3. The Algorithm Error: The small mistake made because they used a finite number of samples to build their "ruler."

They show that by balancing the number of samples used for each step, the total error stays under control.

The Real-World Test: Cryo-Electron Microscopy

To prove their theory isn't just abstract math, they applied it to Cryo-Electron Microscopy (Cryo-EM).

The Context: In Cryo-EM, scientists take 2D pictures of 3D molecules (like viruses) from random angles. These pictures are incredibly noisy.
The Connection: The authors modeled the process of taking these pictures as a mathematical transformation involving rotations (Lie groups) and X-ray projections.
The Result: They proved that the "shape" of all possible clean Cryo-EM images fits the requirements of their algorithm. Specifically, they showed that the mathematical "smoothness" of the molecule's rotation group ensures that the noisy images can be effectively cleaned up using their method.

Summary

In short, the paper says:

Don't fight the noise directly. First, shrink the world down to the dimensions where the signal lives.
Don't chase the jagged edges. Project the data onto a smooth, solid shape (convex hull) that contains the signal.
Use statistics as a ruler. Count the outliers to estimate distances without needing to see the shape clearly.
It's proven. They mathematically guarantee that this process recovers the clean data with a specific, predictable level of accuracy, and they confirmed this logic holds up for the complex, noisy world of 3D molecular imaging.

The paper concludes that while the math is heavy, the logic is sound: by combining geometry, probability, and optimization, we can strip away the "fog" from high-dimensional data and see the hidden structure underneath.

Technical Summary: Denoising Data using Convex Relaxations

Problem Statement
The paper addresses the problem of denoising high-dimensional observations $Y_i = X_i + Z_i$ , where the latent variables $X_i$ are sampled independently from a probability measure $\mu_0$ supported on a low-dimensional manifold $M_0 \subset \mathbb{R}^n$ , and $Z_i$ represents isotropic Gaussian noise ( $Z_i \sim \mathcal{N}(0, \sigma^2 I_n)$ ). The goal is to recover approximations of the clean signals $X_i$ from the noisy observations $Y_i$ without prior knowledge of the manifold structure, relying solely on the data. The framework assumes a "lower-mass condition" on the latent distribution, ensuring that the measure of any ball of radius $\epsilon$ centered on the manifold is bounded below by $c_{M_0} \omega_d \epsilon^d$ .

Methodology
The authors propose a two-stage convex relaxation-based estimator:

Dimensionality Reduction (PCA):
The algorithm first performs Principal Component Analysis (PCA) on a subset of the noisy samples to identify a low-dimensional affine subspace $S$ of dimension $D$ . This step projects the data onto $S$ , effectively eliminating noise in the orthogonal complement. The dimension $D$ is chosen based on the intrinsic dimension $d$ and a user-prescribed error tolerance $\epsilon_0$ .
Convex Projection via a Distance Oracle:
Within the reduced subspace, the algorithm projects the noisy data onto the convex hull $K = \text{conv}(\Pi M_0)$ , where $\Pi$ is the orthogonal projection onto $S$ . Since the manifold $M_0$ and its convex hull $K$ are unknown, the authors utilize a novel statistical distance oracle.
- Oracle Construction: The oracle estimates the Euclidean distance from an affine hyperplane to the latent manifold by analyzing the empirical Gaussian tail mass of the noisy samples falling beyond the hyperplane. It leverages the fact that the probability mass decays exponentially with the distance from the manifold.
- Optimization: Instead of using standard convex optimization subroutines (which the authors note can be costly due to the high sample complexity required for error-free oracle calls), the algorithm performs an exhaustive search over a net in the reduced dimension $D$ to find the projection point that maximizes the distance to the supporting hyperplanes estimated by the oracle.

Key Contributions and Results
The paper provides rigorous finite-sample guarantees for this denoising procedure, decomposing the total recovery error into three distinct components:

PCA Subspace Bias: The geometric error arising from approximating the true manifold $M_0$ with its projection $\Pi M_0$ . The authors prove that with sufficient samples $N_0$ , the Hausdorff distance between $M_0$ and $\Pi M_0$ is bounded by $C_d(4\epsilon_0^2 + 2\epsilon_{\text{emp}})^{1/(d+2)}$ .
Statistical Risk: The fundamental error of projecting onto the convex hull $K$ in the presence of Gaussian noise. By applying Chatterjee's risk bounds for least squares under convex constraints and combining them with Dudley's entropy integral for the convex hull, the authors derive a bound on the projection error scaling with $\sigma J^{1/2} + \sigma \gamma J^{1/4}$ , where $J$ depends on the metric entropy of the projected convex hull.
Algorithmic Error: The error introduced by the finite-sample distance oracle and the exhaustive search. The authors establish the sample complexity required for the oracle to achieve a specific accuracy $\delta$ , showing it scales as $\tilde{\Theta}(\exp(C_d (\sigma/\delta)^2 \log(c_{M_0}^{-1})) \log(\eta^{-1}))$ .

Main Theorem:
The paper establishes that with high probability, the estimated denoised point $\hat{X}_{\text{algo}}$ satisfies:
$\|\hat{X}_{\text{algo}} - X\|_2 \leq \underbrace{C_d(4\epsilon_0^2 + 2\epsilon_{\text{emp}})^{\frac{1}{d+2}}}_{\text{PCA Bias}} + \underbrace{\sigma J^{1/2} + \sigma \gamma J^{1/4}}_{\text{Statistical Risk}} + \underbrace{\epsilon}_{\text{Algorithmic Error}}$
The analysis demonstrates that the noise magnitude is effectively reduced from $\sqrt{n}\sigma$ to a term scaling with the intrinsic dimension and the geometry of the convex hull.

Application to Cryo-Electron Microscopy (Cryo-EM)
The authors instantiate their theoretical framework for Cryo-EM, a domain characterized by extreme noise and continuous symmetries modeled by the Lie group $G = SO(k)$.

They model the data generation process as a smooth group action followed by an X-ray transform and discrete pixel sampling.
They prove that the combined forward operator is Lipschitz continuous.
They verify that the resulting image manifold satisfies the necessary regularity conditions (specifically the lower-mass condition) required for the main theorem, despite the manifold potentially acquiring cusps (non-differentiable points) under the 1-Lipschitz mapping.
Consequently, the framework guarantees finite-sample denoising performance for Cryo-EM projections.

Significance and Claims
The paper claims to provide the first finite-sample guarantees for a denoising procedure that combines PCA dimensionality reduction with projection onto a convex hull estimated via a statistical distance oracle.

Generality: The method does not require the manifold to be $C^{2,1}$ or satisfy specific "exposedness" conditions required by previous manifold fitting works (e.g., Fefferman et al., [5]), allowing it to handle non-differentiable structures like those found in Cryo-EM.
Theoretical Limits: The authors acknowledge that the sample complexity is exponential in the noise parameter $\sigma$ (a known limitation for deconvolution with super-smooth distributions like Gaussians) and that the computational cost of the optimization step is exponential in the reduced dimension $D$ .
Modesty: The paper does not claim to solve the general manifold fitting problem with arbitrary noise levels or to provide polynomial-time optimization algorithms. It explicitly notes that while the sample requirement is exponential in $D$ , the current exhaustive search approach is superior to convex optimization subroutines in the high-cost oracle regime, though improving the computational dependence on $D$ remains an open challenge.

The work bridges statistical learning theory, convex geometry, and geometric analysis, offering a constructive procedure for denoising data where the underlying structure is a low-dimensional manifold with specific mass properties.