A max filtering local stability theorem with application to weighted phase retrieval and cryo-EM

Basic Information

• Paper ID: 2403.14042
• Title: A max filtering local stability theorem with application to weighted phase retrieval and cryo-EM
• Author: Yousef Qaddura (The Ohio State University)
• Classification: math.FA cs.IT math.IT
• Publication Date: March 2024 (arXiv preprint, v3 updated October 13, 2025)
• Paper Link: https://arxiv.org/abs/2403.14042

Abstract

This paper investigates the local bi-Lipschitz properties of max filtering mappings in the framework of inner product spaces $V$ and linear isometry groups $G$. The author identifies sufficient conditions for these convex $G$-invariant mappings to be locally bi-Lipschitz on the regular point set $R(G)$ (the set of orbits with maximum dimension) with respect to the quotient metric on the quotient space $V/G$. The core of the proof is a desingularization theorem applicable to open dense neighborhoods around each orbit in $R(G)/G$. As applications, the paper provides guarantees for stable weighted phase retrieval, constructs componentwise convex bi-Lipschitz embeddings of weighted complex (quaternionic) projective spaces, and discusses the relevance of these embeddings to the nearest neighbor problem in single-particle cryo-EM.

Research Background and Motivation

Core Problem

Modern machine learning algorithms are typically designed for Euclidean data, yet many practical data representations exhibit ambiguities induced by orthogonal symmetry groups $G \leq O(V)$. For example:

• Cryo-EM data may reside in finite-dimensional complex vector spaces $\mathbb{C}^d$, subject to ambiguities induced by diagonal circle actions $S^1 \to \mathbb{C}^{d \times d}$
• Phase retrieval problems with complex equivalence relations $x \sim e^{i\theta}x$

Research Significance

To leverage Euclidean-based machine learning methods, it is necessary to embed the orbit space $V/G$ in a bi-Lipschitz manner into Euclidean space. Such embeddings ensure that distances in $V/G$ are faithfully preserved, enabling Euclidean algorithms to transfer robustly to the orbit space.

Limitations of Existing Approaches

• For finite groups $G$, every injective max filter bank is known to be bi-Lipschitz
• For infinite groups, only three exceptional cases have been resolved: complex phase retrieval, polar coordinate actions
• The bi-Lipschitz property for general infinite groups remains an open problem

Research Motivation

This paper aims to investigate when max filter banks are bi-Lipschitz given sufficiently many generic templates, particularly for group actions where all nonzero orbits have constant dimension.

Core Contributions

1. Established local bi-Lipschitz conditions for max filter banks: On the regular point set $R(G)$, generic max filter banks are locally bi-Lipschitz when the number of templates exceeds $2 \cdot \chi(G) \cdot (c-1)$
2. Proposed a desingularization theorem: Applicable to open dense neighborhoods around each orbit in $R(G)/G$, potentially possessing independent mathematical value
3. Constructed bi-Lipschitz embeddings for stable weighted phase retrieval: Provided componentwise convex bi-Lipschitz embeddings for weighted complex/quaternionic projective spaces
4. Developed Voronoi cell decomposition theory: Provided geometric characterizations of principal and regular points, establishing detailed Voronoi decomposition theory
5. Application to cryo-EM: Provided theoretical guarantees for the nearest neighbor problem in cryo-EM, improving upon existing bispectral embedding methods

Methodology Details

Task Definition

Given an inner product space $V$ and a compact group $G \leq O(V)$, seek templates $z_1, \ldots, z_n \in V$ such that the max filter bank $\Phi([x]) := \{\langle\langle[x], [z_i]\rangle\rangle\}_{i=1}^n$ is a bi-Lipschitz mapping, where the max filtering mapping is defined as: $\langle\langle[x], [z]\rangle\rangle := \sup_{p \in [x], q \in [z]} \langle p, q \rangle$

Core Concepts

Regular Voronoi Complexity

For a compact group $G \leq O(d)$, define:

• Regular point set: $R(G) := \{x \in \mathbb{R}^d : \dim([x]) = \max_{y \in \mathbb{R}^d} \dim([y])\}$
• Regular Voronoi complexity: $\chi(G) := \max_{x,p \in R(G)} \{|G_x/G_p| : G_p \leq G_x\}$

where $G_y$ denotes the stabilizer of $y$ in $G$.

Voronoi Cell Decomposition

For $x \in \mathbb{R}^d$, define:

• Voronoi cell: $U_x := \{z \in \mathbb{R}^d : \{x\} = \arg\max_{p \in [x]} \langle p, z \rangle\}$
• Open Voronoi cell: $V_x := \text{relint}(U_x)$
• Open Voronoi diagram: $Q_x := \bigsqcup_{p \in [x]} V_p$

Main Theorems

Theorem 4 (Local Bi-Lipschitz Property)

Let $G \leq O(d)$ be a compact group and $c := d - \max_{x \in \mathbb{R}^d} \dim([x])$. For generic $z_1, \ldots, z_n \in \mathbb{R}^d$, when $n > 2 \cdot \chi(G) \cdot (c-1)$, the max filter bank $\Phi$ is locally bi-Lipschitz at each $x \in R(G)$.

Theorem 5 (Global Bi-Lipschitz Property)

Let $G \leq O(d)$ be a compact group with $\mathbb{R}^d - \{0\} \subseteq R(G)$, and $c := d - \max_{x \in \mathbb{R}^d} \dim([x])$. For generic $z_1, \ldots, z_n \in \mathbb{R}^d$, when $n > 2 \cdot \chi(G) \cdot (c-1)$, the max filter bank $\Phi$ is bi-Lipschitz.

Technical Innovations

1. Geometric characterization method: Provided geometric characterizations of principal and regular points through Voronoi decomposition
2. Desingularization technique: Constructed local manifold structures for non-manifold orbit spaces
3. Semi-algebraic geometric analysis: Utilized dimension-preserving properties of semi-algebraic sets for complexity analysis
4. Riemannian geometric tools: Combined geodesic and cut locus theory to analyze the geometric properties of orbit spaces

Experimental Setup

Theoretical Verification

The paper is primarily theoretical work, with results verified through:

1. Concrete Example Analysis:
   • Voronoi decomposition of three-dimensional rotation-reflection groups
   • Unitary representations of circle groups on complex spaces
   • Special cases of weighted phase retrieval
2. Dimension Calculations:
   • For complex phase retrieval: $\chi(G) = 1$, $c = 2d-1$
   • For weighted cases: $\chi(G) \leq k_{\max}$, $c \leq p$

Application Verification

Cryo-EM Application

• Problem Scale: $L \times L$ pixel images, $k_{\max} = O(L)$, $p = O(L^2)$
• Template Requirements: $O(L^3)$ generic templates (significant improvement over $O(L^5)$ for bispectral embedding)
• Theoretical Guarantees: Provides explicit bounds on bi-Lipschitz constants

Experimental Results

Main Results

1. Exactness of Dimension Bounds:
   • Proved dimension upper bounds for "bad" template sets
   • Established dimension estimates for semi-algebraic sets
2. Completeness of Voronoi Decomposition:
   • Proved $U_x = V_x$ if and only if specific conditions hold
   • Provided complete characterization of open Voronoi cells
3. Application Effectiveness:
   • Cryo-EM: Reduced complexity from $O(L^5)$ to $O(L^3)$
   • Weighted phase retrieval: Provided stability guarantees

Theoretical Findings

1. Geometric Reciprocity:
   • Principal points: $z \in V_x \Leftrightarrow x \in V_z$
   • Regular points: $z \in V_x \Leftrightarrow x \in V_z^{\text{loc}}$
2. Dimension Relations:
   • Deep connections between regular Voronoi complexity and group structure
   • Dimension-preserving properties of semi-algebraic sets

Related Work

Max Filtering Theory

• Max filter banks concept introduced by Cahill et al.
• Bi-Lipschitz properties for finite groups already resolved
• This paper extends to important cases of infinite groups

Phase Retrieval

• Stability theory for complex phase retrieval
• Generalizations to weighted cases
• New developments in quaternionic cases

Cryo-EM

• Bispectral embedding methods and their limitations
• Approximation of rotational alignment distances
• Fourier-Bessel basis expansions

Conclusions and Discussion

Main Conclusions

1. Under group actions where regular points dominate, sufficiently many generic templates ensure bi-Lipschitz property of max filter banks
2. Voronoi decomposition provides a powerful tool for understanding the geometric structure of orbit spaces
3. Theoretical results have important applications in weighted phase retrieval and cryo-EM

Limitations

1. Open Problems:
   • Is every injective max filter bank bi-Lipschitz in the general case?
   • How to handle local bi-Lipschitz property at non-regular points?
2. Technical Constraints:
   • Requires group action to be nearly free on the unit sphere
   • Lower bounds on template numbers may not be optimal
3. Practical Applications:
   • Cryo-EM applications require numerical verification
   • Practical performance comparison with bispectral embedding remains incomplete

Future Directions

1. Extend analysis to non-regular points
2. Optimize lower bounds on template numbers
3. Numerical experiments to verify theoretical predictions
4. Generalization to more general group actions

In-Depth Evaluation

Strengths

1. Theoretical Depth: Provides important advances in max filtering theory, resolving key problems for infinite groups
2. Technical Innovation: Desingularization theorem and Voronoi decomposition theory possess independent mathematical value
3. Application Value: Provides theoretical guarantees for practical problems (phase retrieval, cryo-EM)
4. Writing Quality: Clear paper structure, rigorous proofs, rich geometric intuition

Weaknesses

1. Insufficient Experimental Verification: Primarily theoretical work lacking numerical experiments
2. Limited Application Scope: The requirement that all nonzero orbits have maximum dimension is restrictive
3. Complexity: Proof techniques are complex, potentially facing computational challenges in practical applications

Impact

1. Academic Contribution: Advances interdisciplinary research between invariant theory and harmonic analysis
2. Practical Value: Provides new tools for handling symmetry in machine learning
3. Reproducibility: Theoretical results are complete, but practical algorithm implementation requires further work

Applicable Scenarios

1. Machine learning problems with group symmetry
2. Phase retrieval and signal processing
3. Rotation invariance problems in computer vision
4. Symmetry reduction in scientific computing

References

The paper includes 22 primary references covering important works in Lie group geometry, harmonic analysis, phase retrieval, and cryo-EM, providing a solid theoretical foundation for this research.

Overall Assessment: This is a high-quality theoretical mathematics paper achieving significant progress in max filtering theory. While primarily a theoretical contribution, it provides important theoretical guarantees for practical applications. The paper demonstrates outstanding technical depth and innovation, though further numerical verification is needed to fully demonstrate its practical value.