The Condition Number of Riemannian Approximation Problems

DOI10.1137/20M1323527MaRDI QIDQ5857299zbMATH OpenWikidataFDO

Authors Paul Breiding, Nick Vannieuwenhoven

Publication date 31 March 2021

Published in SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1909.12186

zbMATH Keywords

condition numberlocal minimizersRiemannian least-squares problemsecond fundamental formsensitivityWeingarten map

Mathematics Subject Classification ID

Differential invariants (local theory), geometric objects (53A55) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Computational issues in computer and robotic vision (65D19) Numerical computation of solutions to systems of equations (65H10) General theory of numerical analysis in abstract spaces (65J05) Sensitivity, stability, parametric optimization (90C31)

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.

Recommendations

• Approximation problems in the Riemannian matric on positive definite metrices
• Conditional extremals in complete Riemannian manifolds
• scientific article; zbMATH DE number 1433472
• scientific article; zbMATH DE number 495713
• Approximations of Riemannian manifolds with linear curvature constraints
• An approximation for a subclass of the Riemann-Hilbert problems
• scientific article; zbMATH DE number 1424580
• Condition numbers and Ritz type methods in unconstrained optimization
• Least squares approximations of measures via geometric condition numbers
• Condition numbers of algebraic Riccati equations in the Frobenius norm

Cites work

• A comprehensive introduction to differential geometry. Vol. 1-5
• A Condition Number for Multifold Conic Systems
• A coordinate-free condition number for convex programming
• A data-independent distance to infeasibility for linear conic systems
• A geometric analysis of Renegar's condition number, and its interplay with conic curvature
• A new condition measure, preconditioners, and relations between different measures of conditioning for conic linear systems
• A new condition number for linear programming
• A primal-dual algorithm for solving polyhedral conic systems with a finite-precision machine
• A Riemannian trust region method for the canonical tensor rank approximation problem
• A Riemannian trust-region method for low-rank tensor completion.
• A Theory of Condition
• Algebraic properties of multilinear constraints
• An Extrinsic Look at the Riemannian Hessian
• COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
• Condition number complexity of an elementary algorithm for computing a reliable solution of a conic linear system
• Condition numbers and error bounds in convex programming
• Condition-Based Complexity of Convex Optimization in Conic Linear Form via the Ellipsoid Algorithm
• Condition. The geometry of numerical algorithms
• Convergence analysis of Riemannian Gauss-Newton methods and its connection with the geometric condition number
• Differential Topology
• Foundations of applied mathematics. Vol. 1. Mathematical analysis
• Geometric measures of convex sets and bounds on problem sensitivity and robustness for conic linear optimization
• scientific article; zbMATH DE number 3842680 (Why is no real title available?)
• scientific article; zbMATH DE number 1229396 (Why is no real title available?)
• scientific article; zbMATH DE number 1012640 (Why is no real title available?)
• scientific article; zbMATH DE number 1024452 (Why is no real title available?)
• scientific article; zbMATH DE number 1049347 (Why is no real title available?)
• scientific article; zbMATH DE number 1077335 (Why is no real title available?)
• scientific article; zbMATH DE number 1565333 (Why is no real title available?)
• scientific article; zbMATH DE number 846277 (Why is no real title available?)
• scientific article; zbMATH DE number 6159604 (Why is no real title available?)
• scientific article; zbMATH DE number 5223994 (Why is no real title available?)
• scientific article; zbMATH DE number 3408799 (Why is no real title available?)
• Ill-Posedness and the Complexity of Deciding Existence of Solutions to Linear Programs
• Implicit Functions and Solution Mappings
• Incorporating Condition Measures into the Complexity Theory of Linear Programming
• Introduction to Smooth Manifolds
• Linear programming, complexity theory and elementary functional analysis
• Low-rank matrix completion by Riemannian optimization
• Low-rank tensor completion by Riemannian optimization
• Manopt, a Matlab toolbox for optimization on manifolds
• Non-Convex Phase Retrieval From STFT Measurements
• Nonconvex phase synchronization
• Numerical stability for solving nonlinear equations
• On an Extension of Condition Number Theory to Nonconic Convex Optimization
• On condition numbers and the distance to the nearest ill-posed problem
• On Intrinsic Cramér-Rao Bounds for Riemannian Submanifolds and Quotient Manifolds
• On manifolds of tensors of fixed TT-rank
• Optimization on the hierarchical Tucker manifold - applications to tensor completion
• Riemannian Geometry
• Riemannian optimization for high-dimensional tensor completion
• Riemannian trust regions with finite-difference Hessian approximations are globally convergent
• Set-valued analysis
• Sur la théorie des enveloppes
• Templates for the Solution of Algebraic Eigenvalue Problems
• The condition number of join decompositions
• The Euclidean distance degree of an algebraic variety
• The Extrinsic Geometry of Dynamical Systems Tracking Nonlinear Matrix Projections
• The geometry of ill-conditioning
• The geometry of multiple images. The laws that govern the formation of multiple images of a scene and some of their applications. With contributions from Théo Papadopoulo
• The Minimum Norm Projection on C 2 -Manifolds in R n
• The normal singularities of a submanifold
• Theory of reconstruction from image motion

Cited in

(10)

• Sensitivity of low-rank matrix recovery
• Learning diagonal Gaussian mixture models and incomplete tensor decompositions
• The average condition number of most tensor rank decomposition problems is infinite
• Algebraic compressed sensing
• scientific article; zbMATH DE number 7688034 (Why is no real title available?)
• The condition number of many tensor decompositions is invariant under Tucker compression
• Line Multiview Varieties
• A note on the rate of convergence of integration schemes for closed surfaces
• Which constraints of a numerical problem cause ill-conditioning?
• Euclidean distance degree in manifold optimization

Describes a project that uses

Uses Software

• mctoolbox
• JDQZ
• Manopt
• JDQR

This page was built for publication: The Condition Number of Riemannian Approximation Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5857299)