Approximation theorems in bilipschitz invariant theory

1. Problem Statement

The paper addresses the problem of bilipschitz invariant theory, which seeks to embed orbit spaces $R^d/G$ (where a finite group $G \le O(d)$ acts on Euclidean space) into a lower-dimensional Euclidean space $R^n$ with minimal metric distortion.

• Context: In group-invariant signal processing and machine learning, one needs feature maps that are invariant to group actions (e.g., rotation, permutation) while preserving the geometric structure of the data.
• Metric: The distortion of a map $f$ is defined as $\text{dist}(f) = \beta(f)/\alpha(f)$, where $\alpha$ and $\beta$ are the lower and upper Lipschitz constants, respectively. The goal is to minimize this ratio.
• The Gap: While the exact Euclidean distortion $c_2(R^d/G)$ is known for three specific cases:
  1. Planar rotations: Finite subgroups of $SO(2)$.
  2. Real phase retrieval: The group $G = \{\pm I\}$.
  3. Finite reflection groups: Groups generated by hyperplane reflections.
     The known optimal embeddings for these cases are often complex and specific. Conversely, max filter banks (a universal method using templates) provide bilipschitz embeddings but generally suffer from a "distortion gap," meaning their distortion is significantly higher than the theoretical optimum $c_2(R^d/G)$.
• Core Question: Can the distortion gap be closed by composing a max filter bank with a linear transformation? Specifically, does the infimal distortion of linear transformations of max filter banks equal the Euclidean distortion?

2. Methodology

The authors employ a two-step proof strategy combining functional analysis and harmonic analysis:

Step 1: Reduction to Function Space Inclusion

Instead of directly optimizing the distortion, the authors reduce the problem to an inclusion of Lipschitz function spaces.

• They define $\text{span } M$ as the linear span of max filter functions $\langle\langle [\cdot], [y] \rangle\rangle$.
• They define $h$ as the known optimal bilipschitz embedding for the specific cases.
• Lemma 4: If the coordinate functions of the optimal map $h$ reside in the Lipschitz closure of the span of max filters, then for any $\epsilon > 0$, there exists a max filter bank composed with a linear map that achieves distortion within $\epsilon$ of the optimal.
• This shifts the problem from optimization to approximation theory: proving that optimal coordinate functions can be approximated arbitrarily well by linear combinations of max filters in the Lipschitz norm.

Step 2: Proving the Inclusion via Integral Representations

The authors prove that the coordinate functions of the optimal maps lie in the Lipschitz closure of max filters by expressing them as integral combinations of max filters.

• Theorem 13: If a function $p$ can be written as $p(x) = \int q(y) \langle\langle [x], [y] \rangle\rangle d\omega(y)$ for a Lipschitz weight function $q$, then $p$ is in the Lipschitz closure of the span of max filters.
• Case (a) Planar Rotations ($d=2$): They use Fourier series on the circle $S^1$ to show that optimal coordinate functions (which are trigonometric polynomials) can be represented as convolutions of max filters with specific coefficients.
• Case (b) Real Phase Retrieval ($G=\{\pm I\}$): They utilize the theory of spherical harmonics and Gegenbauer polynomials. They show that even polynomials on the sphere can be represented as integrals of absolute inner products (max filters for this group) against specific polynomial weights.
• Case (c) Reflection Groups: They use a geometric argument. For reflection groups, the optimal map $h$ (projection onto a Weyl chamber) is shown to be exactly a linear combination of max filters, not just an approximation.

3. Key Contributions

1. Main Theorem (Theorem 3): For the three specific cases mentioned above, the authors prove that the optimal distortion $c_2(R^d/G)$ is nearly achieved (or exactly achieved in the reflection case) by a composition of a max filter bank and a linear map.

   • Significance: This suggests a universal architecture: "Max Filter Bank + Linear Layer" is sufficient to achieve near-optimal metric preservation for these groups.

2. Structural Analysis of Function Spaces (Theorem 5): The paper provides a deep structural characterization of the relationship between:

   • Optimal coordinate functions ($\text{span}\{h_i\}$).
   • Max filter spans ($\text{span } M$).
   • Invariant polynomials ($\text{ext } P_G$).
   • Piecewise linear invariant functions ($PL^G_h$).
   • Key Finding: The relationship between these spaces is case-dependent.
     • For rotations and phase retrieval, the optimal functions are in the closure of max filters but not in the span of polynomials or piecewise linear functions in a simple way.
     • For reflection groups, the optimal functions are exactly in the span of max filters.
     • This implies there is no single "unified" proof for all groups; the mechanisms differ fundamentally.

3. Dimensionality Reduction Insight: The authors highlight a qualitative difference from previous work. While previous theorems showed that linear maps preserve injectivity ("it doesn't hurt"), this work shows that linear maps reduce distortion ("it helps"). The linear layer performs substantial dimensionality reduction that is crucial for achieving low distortion.

4. Results

Theoretical Results

• Planar Rotations: The optimal embedding is the Lipschitz closure of max filters.
• Real Phase Retrieval: The optimal embedding (operator square root) is the Lipschitz closure of max filters.
• Reflection Groups: The optimal embedding (projection to Weyl chamber) is exactly a linear transformation of a max filter bank (with $\epsilon=0$).

Numerical Experiments

The authors conducted extensive numerical experiments to test if this phenomenon generalizes beyond the three proven cases:

• Architectures Tested: Trained Max Filter Banks (MF), Linear Layer + Random Max Filter (LRMF), Linear Layer + Trained Max Filter (LMF), and standard ReLU networks.
• Datasets: Various orbit spaces including $R^3/\{\pm I\}$, $C^2/S^1$, and real-world data like U.S. congressional districts and 2D shape structures.
• Findings:
  • The LMF (Linear Layer + Max Filter) architecture consistently achieved the lowest empirical distortion among invariant methods.
  • In cases where the optimal distortion is known (e.g., $R^2/\{\pm I\}$), LMF approached the theoretical limit ($\sqrt{2}$), whereas raw max filter banks (MF) remained stuck at a higher distortion ($\approx 1.66$).
  • LMF outperformed standard ReLU networks in many invariant settings, suggesting that the specific structure of max filters combined with linear layers is superior for group-invariant learning.
  • Visualizations of congressional districts showed that the LMF embedding captured geometric properties like convexity and eccentricity, separating gerrymandered districts effectively.

5. Significance and Future Directions

• Theoretical Impact: The paper bridges the gap between abstract invariant theory and practical machine learning architectures. It provides a rigorous justification for using max filter banks followed by linear layers as a near-optimal strategy for metric preservation.
• Practical Impact: It suggests that for group-invariant signal processing, one should not just use max filters, but specifically train a linear layer on top of them. This is a lightweight, interpretable alternative to deep neural networks that respects group symmetries.
• Open Problems:
  • Does this hold for all closed subgroups of $O(d)$?
  • Can a unified proof be found for the inclusion of function spaces across different group types?
  • Characterizing the closure of max filter spans for general groups (Problem 7).

In summary, the paper demonstrates that the "gap" between the theoretical best distortion and the distortion of max filter banks is an artifact of using the filters alone; adding a linear transformation closes this gap, offering a powerful, theoretically grounded tool for invariant machine learning.