The condition number of Riemannian approximation problems

Abstract

We consider the local sensitivity of least-squares formulations of inverse problems. The sets of inputs and outputs of these problems are assumed to have the structures of Riemannian manifolds. The problems we consider include the approximation problem of finding the nearest point on a Riemannian embedded submanifold from a given point in the ambient space. We characterize the first-order sensitivity, i.e., condition number, of local minimizers and critical points to arbitrary perturbations of the input of the least-squares problem. This condition number involves the Weingarten map of the input manifold, which measures the amount by which the input manifold curves in its ambient space. We validate our main results through experiments with the $n$-camera triangulation problem in computer vision.

References in corpus (1)

• Structured Compressed Sensing: From Theory to Applications

Cited by in corpus (6)

• Algebraic compressed sensing
• Sensitivity of low-rank matrix recovery
• The average condition number of most tensor rank decomposition problems is infinite
• The condition number of many tensor decompositions is invariant under Tucker compression
• Which constraints of a numerical problem cause ill-conditioning?
• Learning Diagonal Gaussian Mixture Models and Incomplete Tensor Decompositions