Technical Summary: Robust Subspace-Constrained Quadratic Models for Low-Dimensional Structure Learning

Problem Statement

Learning low-dimensional structures from high-dimensional data is a fundamental challenge in machine learning and signal processing. Traditional methods, such as local linear fitting, kernel density estimation (KDE), and principal curves, often rely on the assumption that data resides in a linear subspace perturbed by Gaussian noise. These assumptions are frequently unrealistic in real-world scenarios where data may lie on complex nonlinear manifolds and be corrupted by heavy-tailed noise or outliers.

Existing quadratic factorization models, such as Subspace-Constrained Quadratic Matrix Factorization (SQMF), improve upon linear models by capturing curvature through second-order terms. However, they typically rely on squared Euclidean loss (Frobenius norm), which assumes Gaussian noise. This makes them highly sensitive to outliers and misspecifications. Furthermore, selecting appropriate penalty parameters to mitigate overfitting in these models remains a difficult task. There is a need for a framework that accommodates a broader class of noise distributions (including heavy-tailed and light-tailed) while maintaining the expressive power of quadratic manifold representations.

Methodology

The authors propose a Robust Subspace-Constrained Quadratic Model (SCQM) that generalizes the SQMF framework to accommodate a broad class of loss functions corresponding to various noise distributions.

1. Model Formulation

The model assumes data points $x_i \in \mathbb{R}^D$ are generated by a quadratic mapping $f(\tau_i)$ plus noise $\epsilon_i$:
$$x_i = f(\tau_i) + \epsilon_i$$
The mapping $f$ is restricted to a class of quadratic functions with explicit tangent and normal space representations:
$$f(\tau) = c + U\tau + V A(\tau, \tau)$$
where:

• $c$ is a shift parameter.
• $U \in \mathbb{R}^{D \times d}$ and $V \in \mathbb{R}^{D \times s}$ are orthonormal bases for the tangent and normal subspaces, respectively, satisfying $U^\top U = I_d$, $V^\top V = I_s$, and $U^\top V = 0$.
• $A(\tau, \tau)$ represents the quadratic interaction, parameterized by a tensor $A$ or a matrix $\Theta$ acting on the vectorized upper-triangular part of $\tau\tau^\top$.
• The orthogonality constraints are compactly represented by $Q = [U, V] \in \text{St}(d+s, D)$.

The learning objective minimizes a general loss function $\ell(\cdot)$:
$$\min_{f, \{\tau_i\}} \sum_{i=1}^n \ell(x_i - f(\tau_i))$$
The choice of $\ell(\cdot)$ is aligned with the noise distribution:

• Gaussian noise: $\ell(r) = \|r\|_2^2$ (Squared Euclidean).
• Radial Laplace noise: $\ell(r) = \|r\|_2$.
• Generalized Gaussian noise: $\ell(r) = \|r\|_p^p$ (where $p \ge 1$). Smaller $p$ values provide robustness to heavy-tailed noise.

2. Optimization Algorithm

The resulting optimization problem is nonconvex due to the quadratic structure and orthogonality constraints on the Stiefel manifold. The authors develop a Riemannian Gradient Descent algorithm with the following features:

• Gradient Derivation: Closed-form expressions are derived for the gradients with respect to latent coordinates $\tau$, the quadratic parameters $\Theta$, the shift $c$, and the basis $Q$. Special attention is given to the non-trivial gradient of the quadratic term involving the vech operator.
• Riemannian Updates: For the variable $Q$, updates are performed on the Stiefel manifold. The Euclidean gradient is projected onto the tangent space, followed by a retraction using an aligned QR decomposition to ensure orthogonality is preserved.
• Backtracking Line Search: An asynchronous learning-rate adjustment strategy based on the Armijo rule is employed for each variable block ($c, Q, \Theta, \tau$) to ensure stable and efficient convergence.

3. Theoretical Analysis

• Identifiability: The paper establishes that while the parameters are identifiable only up to orthogonal transformations in the latent space, the learned mapping $f(\cdot)$ and the associated quadratic manifold are uniquely determined within these equivalence classes.
• Convexity: The subproblems for $c$ and $\Theta$ (with fixed $\tau$) are convex. The convexity of the subproblem for $\tau$ is analyzed via the Hessian; the authors derive a local convexity radius showing that the Hessian remains positive definite under bounded noise and curvature conditions.
• Sensitivity Analysis: Using the Implicit Function Theorem, the authors analyze the sensitivity of the Fréchet mean (a simplified version of the model) to data perturbations. They demonstrate that $\ell_p^p$ losses ($1 < p \le 2$) and $\ell_2$ losses yield estimators with bounded sensitivity to outliers, unlike the squared $\ell_2^2$ loss where sensitivity grows linearly with residual magnitude.

Key Contributions

1. Generalized Framework: Proposal of a robust SCQM framework extending SQMF to a broad class of loss functions (including $\ell_p^p$ and $\ell_2$), enabling adaptation to both heavy-tailed and light-tailed noise.
2. Theoretical Insight: Derivation of explicit gradients for all variables and a theoretical analysis (based on the implicit function theorem) explaining why non-squared norms improve robustness by attenuating the influence of large residuals.
3. Algorithm Development: Development of an efficient Riemannian gradient descent algorithm with orthogonality-preserving updates on the Stiefel manifold and asynchronous backtracking line search.
4. Empirical Validation: Extensive numerical experiments demonstrating superior robustness and reconstruction accuracy compared to existing methods (SPH, MFIT, MLS) and linear variants, particularly in the presence of outliers.

Experimental Results

The authors validate the method on synthetic and real-world datasets:

• Synthetic Data (Sphere in $\mathbb{R}^3$): The SCQM model consistently outperforms state-of-the-art methods (SPH, MFIT, MLS) across varying noise levels ($\sigma \in [0.03, 0.18]$).
  • In low-noise regimes, quadratic models outperform linear ones, validating the utility of curvature terms.
  • In high-noise regimes, smaller $p$ values in $\ell_p^p$ loss provide superior robustness, though extremely small $p$ (e.g., $p=1$) may underperform in very low-noise settings due to projection mismatch.
  • The $\ell_2$ loss offers a stable, balanced performance across noise levels.
• Real-World Data (MNIST): Applied to handwritten digits '4' and '9', the SCQM with $\ell_1$ and $\ell_2$ losses produced sharper and more visually coherent reconstructions compared to the squared $\ell_2^2$ loss and linear variants.
• Interpolation: The model demonstrated superior expressive capability in latent space interpolation, generating smoother transitions between digit classes ('2', '6', '8') compared to linear models, effectively capturing intrinsic geometric structures.

Significance and Claims

The paper claims that the proposed SCQM framework addresses the limitations of traditional linear and Gaussian-assumption-based models by providing a flexible, robust approach to learning low-dimensional structures. By generalizing the loss function, the model can adapt to diverse noise characteristics without sacrificing the ability to model nonlinear manifolds. The authors assert that this approach offers enhanced robustness and reconstruction accuracy in practical scenarios where Gaussian assumptions fail, making it a valuable tool for manifold denoising and data refinement.

The work concludes by noting that while the method shows stable empirical behavior, future research is needed to establish non-asymptotic statistical properties, provide theoretical convergence guarantees for the algorithm, and explore extensions to even richer nonlinear structures.