The generalized orthogonal Procrustes problem in the high noise regime

Thomas Pumir, Amit Singer, Nicolas Alain S. Boumal

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

We consider the problem of estimating a cloud of points from numerous noisy observations of that cloud after unknown rotations and possibly reflections. This is an instance of the general problem of estimation under group action, originally inspired by applications in three-dimensional imaging and computer vision. We focus on a regime where the noise level is larger than the magnitude of the signal, so much so that the rotations cannot be estimated reliably. We propose a simple and efficient procedure based on invariant polynomials (effectively: the Gram matrices) to recover the signal, and we assess it against fundamental limits of the problem that we derive. We show our approach adapts to the noise level and is statistically optimal (up to constants) for both the low and high noise regimes. In studying the variance of our estimator, we encounter the question of the sensivity of a type of thin Cholesky factorization, for which we provide an improved bound which may be of independent interest.

Original languageEnglish (US)
Pages (from-to)921-954
Number of pages34
JournalInformation and Inference
Volume10
Issue number3
DOIs
StatePublished - Sep 1 2021

All Science Journal Classification (ASJC) codes

  • Analysis
  • Statistics and Probability
  • Numerical Analysis
  • Computational Theory and Mathematics
  • Applied Mathematics

Keywords

  • Cholesky factorization
  • Procrustes

Fingerprint

Dive into the research topics of 'The generalized orthogonal Procrustes problem in the high noise regime'. Together they form a unique fingerprint.

Cite this