Goodness-of-Fit Tests on Manifolds

Alexander Shapiro, Yao Xie, Rui Zhang

TL;DR

This paper introduces a general theory for testing how well non-linear models fit noisy data that lies on a manifold. The core idea is that the residuals from a least-squares fit follow a chi-squared distribution, allowing for a principled way to select model complexity, like the rank of a matrix or the number of hidden units in a neural network. This framework offers a statistically rigorous alternative to heuristic methods in various machine learning and signal processing tasks.

What Problem Does This Paper Address?

In statistics and signal processing, determining how well a model fits observed data (goodness-of-fit) is crucial for tasks like model selection and diagnosis. While well-established methods exist for linear models, the problem becomes significantly more challenging for non-linear models, especially when the data is assumed to lie on an underlying manifold (a curved, lower-dimensional structure within a higher-dimensional space). Many real-world applications, such as low-rank matrix completion, signal demixing, and neural network architecture design, involve such non-linear manifold structures and noisy observations. Existing methods for model order selection in these complex scenarios often rely on heuristics or computationally intensive simulations. This paper aims to bridge this gap by providing a general theoretical framework for goodness-of-fit testing on manifolds, enabling principled model order selection.

Methods

The paper's central contribution is the development of a general theory for goodness-of-fit tests on manifolds. The key assumption is that observations are noisy samples of a submanifold defined by a smooth non-linear map, with additive Gaussian noise. The core result is that the "residual" obtained from fitting a non-linear least-squares problem follows a (possibly non-central) chi-squared ($\chi^2$) distribution. The parameters of this $\chi^2$ distribution are directly related to the model's intrinsic dimension and the manifold's characteristic rank (the maximum rank of the Jacobian matrix of the mapping defining the manifold).

This theoretical insight leads to a practical sequential test procedure for model order selection. By comparing the $\chi^2$ statistics for nested models (models of increasing complexity), one can statistically determine the appropriate model order. The authors also introduce the concept of a "well-posed" model, which is crucial for ensuring the identifiability and statistical properties of the model.

Datasets

The paper does not introduce new datasets. Instead, it demonstrates the application of its theoretical framework to established problems in machine learning and signal processing, using simulated data for evaluation. These applications include:

  • Noisy Matrix Completion: Generating synthetic low-rank matrices with additive noise.
  • Complex Noisy Matrix Completion: Similar to real matrix completion but with complex-valued matrices.
  • Matrix Sensing: Simulating data from one-hidden-layer neural networks with quadratic activation.
  • Low-Rank Matrix Sensing: Simulating data from one-hidden-layer neural networks with sigmoid activation.
  • Blind De-mixing: Generating synthetic signals with unknown sources, delays, and noise.
  • Tensor Completion: Generating synthetic third-order tensors.
  • One-Hidden-Layer Neural Networks: Simulating data from networks with quadratic, sigmoid, and ReLU activation functions.

Key Insights and Ideas

  • The $\chi^2$ Distribution as a Universal Tool: The surprising universality of the $\chi^2$ distribution for model residuals on manifolds provides a powerful statistical tool for model selection, unifying various problems under a single theoretical umbrella.
  • Characteristic Rank is Key: The "characteristic rank" of the mapping defining the manifold emerges as a critical parameter, directly influencing the degrees of freedom and non-centrality parameter of the $\chi^2$ distribution. This rank dictates the intrinsic dimensionality of the manifold.
  • Principled Model Order Selection: The framework moves beyond heuristic approaches by offering a statistically rigorous method for selecting model complexity (e.g., matrix rank, number of hidden units) based on hypothesis testing.
  • Well-Posedness for Identifiability: The concept of a "well-posed" model is introduced as a necessary condition for ensuring that the model parameters are uniquely identifiable, which is crucial for the validity of the statistical tests.
  • Broad Applicability: The theory is shown to be applicable across a wide range of challenging problems, including matrix and tensor completion, signal demixing, and neural network architecture design, highlighting its practical significance.

Key Results

The paper presents several key theoretical and empirical results:

  • Theoretical Result: The core theoretical result is that the least-squares residual for a model on a manifold, under additive Gaussian noise, asymptotically follows a non-central $\chi^2$ distribution.
  • Model Order Selection: The proposed goodness-of-fit test statistic allows for sequential model order selection. For instance, in experiments with complex matrix completion, the test correctly identified the true rank in a high percentage of cases (e.g., 96% for true rank 3, with a false rejection rate close to the significance level).
  • Characteristic Rank Formulas: The paper provides or empirically verifies formulas for the characteristic rank in various applications, such as:
  • Matrix completion: $r(n_1 + n_2 - r)$ for real matrices.
  • Complex matrix completion: $2r(n_1 + n_2 - r)$.
  • One-hidden-layer neural networks (quadratic activation): $dr - r(r-1)/2$.
  • One-hidden-layer neural networks (sigmoid activation): $dr$.
  • Blind de-mixing: $2K + NK - 1$ (where K is the number of sources, N is the number of sensors).
  • Empirical Validation: Extensive numerical experiments across various applications (matrix completion, tensor completion, neural networks, blind de-mixing) demonstrate that the proposed test statistics align well with the theoretical $\chi^2$ distributions and effectively determine model orders. For example, in blind de-mixing, the test accurately identified the number of sources in most experimental settings.

Limitations and Future Work

  • Analytic Assumption: The theoretical derivations often rely on the assumption that the mapping defining the manifold is analytic. While the paper shows promising results for non-analytic functions like ReLU in neural networks, a deeper theoretical understanding for such cases is still needed.
  • Computational Complexity: Evaluating the characteristic rank, especially for complex scenarios like tensor decomposition, can be computationally intensive. The paper mentions that explicit formulas are not always available and numerical computation of the Jacobian rank is used.
  • Global Identifiability: While local identifiability is addressed, verifying global identifiability for non-linear models remains a challenging problem, which is acknowledged as beyond the scope of this paper.
  • Future Work: The authors suggest exploring more complex manifold structures, developing more efficient algorithms for characteristic rank computation, and further investigating the identifiability of models in various applications. They also highlight the potential for using their framework to estimate unknown noise variances, which is demonstrated with preliminary results.

Summary updated

Abstract

We develop a general theory for the goodness-of-fit test to non-linear models. In particular, we assume that the observations are noisy samples of a submanifold defined by a sufficiently smooth non-linear map. The observation noise is additive Gaussian. Our main result shows that the “residual” of the model fit, by solving a non-linear least-square problem, follows a (possibly noncentral) χ <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> distribution. The parameters of the χ <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> distribution are related to the model order and dimension of the problem. We further present a method to select the model orders sequentially. We demonstrate the broad application of the general theory in machine learning and signal processing, including determining the rank of low-rank (possibly complex-valued) matrices and tensors from noisy, partial, or indirect observations, determining the number of sources in signal demixing, and potential applications in determining the number of hidden nodes in neural networks.
BibTeX
@misc{shapiro2019goodness,
  author = {Alexander Shapiro and Yao Xie and Rui Zhang},
  title = {{Goodness-of-Fit Tests on Manifolds}},
  year = {2019},
  eprint = {1909.05229},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1909.05229},
}
Figure