The condition number of Riemannian approximation problems. (English) Zbl 1462.90133


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


Manopt; mctoolbox; JDQR; JDQZ
Full Text: DOI arXiv


[1] T. J. Abatzoglou, The minimum norm projection on \(C^2\) manifolds in \(R^n\), Trans. Amer. Math. Soc., 243 (1978), pp. 115-122, https://doi.org/10.2307/1997757. · Zbl 0382.41019
[2] P.-A. Absil, R. Mahony, and R. Sepulchre, Optimization Algorithms on Matrix Manifolds, Princeton University Press, Princeton, NJ, 2008, https://doi.org/10.1515/9781400830244. · Zbl 1147.65043
[3] P.-A. Absil, R. Mahony, and J. Trumpf, An extrinsic look at the Riemannian Hessian, in Geometric Science of Information, Lecture Notes in Comput. Sci. 8085, Springer, New York, 2013, pp. 361-368, https://doi.org/10.1007/978-3-642-40020-9_39. · Zbl 1323.53014
[4] D. Amelunxen and P. Bürgisser, A coordinate-free condition number for convex programming, SIAM J. Optim., 22 (2012), pp. 1029-1041, https://doi.org/10.1137/110835177. · Zbl 1266.90139
[5] J.-P. Aubin and H. Frankowska, Set-Valued Analysis, Birkhäuser Boston, Boston, MA, 2009. · Zbl 1168.49014
[6] Z. Bai, J. Demmel, J. Dongarra, A. Ruhe, and H. van der Vorst, eds., Templates for the Solution of Algebraic Eigenvalue Problems: A Practical Guide, Software Environ. Tools 11, SIAM, Philadelphia, 2000. · Zbl 0965.65058
[7] D. Bau and L. N. Trefethen, Numerical Linear Algebra, SIAM, 1997, https://doi.org/10.1137/1.9780898719574. · Zbl 0874.65013
[8] A. Belloni and R. M. Freund, A geometric analysis of Renegar’s condition number, and its interplay with conic curvature, Math. Program. Ser. A, 119 (2009), pp. 95-107, https://doi.org/10.1007/s10107-007-0203-8. · Zbl 1163.90029
[9] T. Bendory, Y. C. Eldar, and N. Boumal, Non-convex phase retrieval from STFT measurements, IEEE Trans. Inform. Theory, 64 (2018), pp. 467-484, https://doi.org/10.1109/TIT.2017.2745623. · Zbl 1390.94093
[10] L. Blum, F. Cucker, M. Shub, and S. Smale, Complexity and Real Computation, Springer, New York, 1998, https://doi.org/10.1007/978-1-4612-0701-6. · Zbl 0872.68036
[11] N. Boumal, Riemannian trust regions with finite-difference Hessian approximations are globally convergent, in Geometric Science of Information, Vol. 2, F. Nielsen and F. Barbaresco, eds., Lecture Note in Comput. Sci. 9389, Springer, New York, 2015, pp. 467-475, https://doi.org/10.1007/978-3-319-25040-3_50. · Zbl 1405.90124
[12] N. Boumal, Nonconvex phase synchronization, SIAM J. Optim., 26 (2016), pp. 2355-2377, https://doi.org/10.1137/16m105808x. · Zbl 1356.90111
[13] N. Boumal, An Introduction to Optimization on Smooth Manifolds, http://www.nicolasboumal.net/book, 2020. · Zbl 1393.94653
[14] N. Boumal, B. Mishra, P.-A. Absil, and R. Sepulchre, Manopt, a MATLAB toolbox for optimization on manifolds, J. Mach. Learn. Res., 15 (2014), pp. 1455-1459, http://www.manopt.org. · Zbl 1319.90003
[15] P. Breiding and N. Vannieuwenhoven, The condition number of join decompositions, SIAM J. Matrix Anal. Appl., 39 (2018), pp. 287-309, https://doi.org/10.1137/17m1142880. · Zbl 1384.49035
[16] P. Breiding and N. Vannieuwenhoven, Convergence analysis of Riemannian Gauss-Newton methods and its connection with the geometric condition number, Appl. Math. Lett., 78 (2018), pp. 42-50, https://doi.org/10.1016/j.aml.2017.10.009. · Zbl 1381.65043
[17] P. Breiding and N. Vannieuwenhoven, Sensitivity of Low-Rank Matrix Recovery, arXiv:2103.00531, 2021, https://arxiv.org/abs/2103.00531. · Zbl 1397.15022
[18] P. Bürgisser and F. Cucker, Condition: The Geometry of Numerical Algorithms, Springer, New York, 2013. · Zbl 1280.65041
[19] N. Chernov and H. Ma, Least squares fitting of quadratic curves and surfaces, in Computer Vision, S. Yoshida, ed., Nova Science Publishers, Hauppauge, NY, 2011, pp. 285-302.
[20] D. Cheung and F. Cucker, A new condition number for linear programming, Math. Program., 91 (2001), pp. 163-174, https://doi.org/10.1007/s101070100237. · Zbl 1072.90564
[21] D. Cheung, F. Cucker, and J. Pen͂a, A condition number for multifold conic systems, SIAM J. Optim., 19 (2008), pp. 261-280, https://doi.org/10.1137/060665427. · Zbl 1168.90572
[22] A. Coulibaly and J.-P. Crouzeix, Condition numbers and error bounds in convex programming, Math. Program., 116 (2009), pp. 79-113, https://doi.org/10.1007/s10107-007-0132-6. · Zbl 1167.90012
[23] F. Cucker and J. Pen͂a, A primal-dual algorithm for solving polyhedral conic systems with a finite-precision machine, SIAM J. Optim., 12 (2001), pp. 522-554, https://doi.org/10.1137/s1052623401386794. · Zbl 0996.90052
[24] C. Da Silva and F. J. Herrmann, Optimization on the hierarchical Tucker manifold-applications to tensor completion, Linear Algebra Appl., 481 (2015), pp. 131-173, https://doi.org/10.1016/j.laa.2015.04.015. · Zbl 1317.65136
[25] J. W. Demmel, The geometry of ill-conditioning, J. Complexity, 3 (1987), pp. 201-229, https://doi.org/10.1016/0885-064X(87)90027-6.
[26] J. W. Demmel, On condition numbers and the distance to the nearest ill-posed problem, Numer. Math., 51 (1987), pp. 251-289, https://doi.org/10.1007/bf01400115. · Zbl 0597.65036
[27] J. W. Demmel, Applied Numerical Linear Algebra, SIAM, 1997, https://doi.org/10.1137/1.9781611971446. · Zbl 0879.65017
[28] M. do Carmo, Riemannian Geometry, Birkhäuser, Basel, 1993.
[29] A. L. Dontchev and R. T. Rockafeller, Implicit Functions and Solution Mappings: A View from Varational Analysis, Springer Monogr. Math., Springer, New York, 2009.
[30] J. Draisma, E. Horobet, G. Ottaviani, B. Sturmfels, and R. Thomas, The Euclidean distance degree of an algebraic variety, Found. Comput. Math., 16 (2016), pp. 99-149, https://doi.org/10.1007/s10208-014-9240-x. · Zbl 1370.51020
[31] M. Epelman and R. M. Freund, Condition number complexity of an elementary algorithm for computing a reliable solution of a conic linear system, Math. Program., 88 (2000), pp. 451-485, https://doi.org/10.1007/s101070000136. · Zbl 0989.65061
[32] M. Epelman and R. M. Freund, A new condition measure, preconditioners, and relations between different measures of conditioning for conic linear systems, SIAM J. Optim., 12 (2002), pp. 627-655, https://doi.org/10.1137/s1052623400373829. · Zbl 1046.90038
[33] O. Faugeras and Q. Luong, The Geometry of Multiple Images, MIT Press, Cambridge, MA, 2001, https://doi.org/10.7551/mitpress/3259.001.0001. · Zbl 1002.68183
[34] F. Feppon and P. F. J. Lermusiaux, The extrinsic geometry of dynamical systems tracking nonlinear matrix projections, SIAM J. Matrix Anal. Appl., 40 (2019), pp. 814-844, https://doi.org/10.1137/18m1192780. · Zbl 07099843
[35] R. M. Freund and F. Ordón͂ez, On an extension of condition number theory to nonconic convex optimization, Math. Oper. Res., 30 (2005), pp. 173-194, https://doi.org/10.1287/moor.1040.0120. · Zbl 1082.90151
[36] R. M. Freund and J. R. Vera, Condition-based complexity of convex opitimization in conic linear form via the ellipsoid algorithm, SIAM J. Optim., 10 (1999), pp. 155-176, https://doi.org/10.1137/s105262349732829x. · Zbl 0953.90044
[37] G. H. Golub and C. Van Loan, Matrix Computations, 4th ed., John Hopkins University Press, Baltimore, 2013. · Zbl 1268.65037
[38] R. Hartley and A. Zisserman, Multiple View Geometry in Computer Vision, 2nd ed., Cambridge University Press, Cambridge, UK, 2003. · Zbl 0956.68149
[39] G. Heidel and V. Schulz, A Riemannian trust-region method for low-rank tensor completion, Numer. Linear Algebra Appl., 25 (2018), https://doi.org/10.1002/nla.2175. · Zbl 07031737
[40] A. Heyden and K. \AAström, Algebraic properties of multilinear constraints, Math. Methods Appl. Sci., 20 (1997), pp. 1135-1162, https://doi.org/10.1002/(sici)1099-1476(19970910)20:13<1135::aid-mma908>3.0.co;2-9.
[41] N. Higham, Accuracy and Stability of Numerical Algorithms, SIAM, Philadelphia, 1996. · Zbl 0847.65010
[42] M. W. Hirsch, Differential Topology, Grad. Texts in Math. 33, Springer, New York, 1976.
[43] S. Holtz, T. Rohwedder, and R. Schneider, On manifolds of tensors of fixed TT-rank, Numer. Math., 120 (2012), pp. 701-731, https://doi.org/10.1007/s00211-011-0419-7. · Zbl 1242.15022
[44] J. Humpherys, T. J. Jarvis, and E. J. Evans, Foundations of Applied Mathematics, SIAM, Philadelphia, 2017. · Zbl 1375.00006
[45] D. Kressner, M. Steinlechner, and B. Vandereycken, Low-rank tensor completion by Riemannian optimization, BIT, 54 (2014), pp. 447-468, https://doi.org/10.1007/s10543-013-0455-z. · Zbl 1300.65040
[46] Z. Kúkelová, Algebraic Methods in Computer Vision, Ph.D. thesis, Czech Technical University, Prague, 2013.
[47] J. M. Lee, Riemannian Manifolds: Introduction to Curvature, Springer, New York, 1997. · Zbl 0905.53001
[48] J. M. Lee, Introduction to Smooth Manifolds, 2nd ed., Springer, New York, 2013. · Zbl 1258.53002
[49] Y. Liu and W. Wang, A revisit to least squares orthogonal distance fitting of parametric curves and surfaces, in Advances in Geometric Modeling and Processing, F. Chen and B. Juttler, eds., Lecture Notes in Comput. Sci. 4975, Springer, New York, 2008, pp. 384-397.
[50] S. Maybank, Theory of Reconstruction from Image Motion, Springer Ser. Inform. Sci. 28, Springer, New York, 1993. · Zbl 0875.68956
[51] B. O’Neill, Semi-Riemannian Geometry, Academic Press, New York, 1983.
[52] B. O’Neill, Elementary Differential Geometry, 2nd ed., Elsevier, Amsterdam, 2001, https://doi.org/10.1090/chel/341/01.
[53] J. Pen͂a and V. Roshchina, A data-independent distance to infeasibility for linear conic systems, SIAM J. Optim., 30 (2020), pp. 1049-1066, https://doi.org/10.1137/18m1189464. · Zbl 1437.90120
[54] P. Petersen, Riemannian Geometry, 2nd ed., Grad. Texts in Math. 171, Springer, New York, 2006.
[55] I. R. Porteous, The normal singularities of a submanifold, J. Differential Geom., 5 (1971), pp. 543-564, https://doi.org/10.4310/jdg/1214430015. · Zbl 0226.53010
[56] M. Psenka and N. Boumal, Second-order optimization for tensors with fixed tensor-trains rank, in Proceedings of OPT2020: 12th Annual Workshop on Optimization for Machine Learning, 2020.
[57] J. Renegar, Incorporating condition measures into the complexity theory of linear programming, SIAM J. Optim., 5 (1995), pp. 506-524, https://doi.org/10.1137/0805026. · Zbl 0838.90139
[58] J. Renegar, Linear programming, complexity theory and elementary functional analysis, Math. Program., 70 (1995), pp. 279-351, https://doi.org/10.1007/bf01585941. · Zbl 0855.90085
[59] J. R. Rice, A theory of condition, SIAM J. Numer. Anal., 3 (1966), pp. 287-310, https://doi.org/10.1137/0703023. · Zbl 0143.37101
[60] M. Spivak, A Comprehensive Introduction to Differential Geometry, Vol. 2, Publish or Perish, 1999. · Zbl 1213.53001
[61] M. Steinlechner, Riemannian optimization for high-dimensional tensor completion, SIAM J. Sci. Comput., 38 (2016), pp. S461-S484, https://doi.org/10.1137/15m1010506. · Zbl 1352.65129
[62] A. Sung-Joon, Geometric fitting of parametric curves and surfaces, J. Inform. Process. Syst., 4 (2008), pp. 153-158, https://doi.org/10.3745/jips.2008.4.4.153.
[63] R. Thom, Sur la theorie des enveloppes, J. Math. Pures Appl., 41 (1962), pp. 177-192. · Zbl 0105.16102
[64] A. Uschmajew, Zur Theorie der Niedrigrangapproximation in Tensorprodukten von Hilberträumen, Ph.D. thesis, TU Berlin, 2013.
[65] B. Vandereycken, Low-rank matrix completion by Riemannian optimization, SIAM J. Optim., 23 (2013), pp. 1214-1236, https://doi.org/10.1137/110845768. · Zbl 1277.15021
[66] J. R. Vera, Ill-posedness and the complexity of deciding existence of solutions to linear programs, SIAM J. Optim., 6 (1996), pp. 549-569, https://doi.org/10.1137/s105262349223352x. · Zbl 0856.90077
[67] J. R. Vera, Geometric measures of convex sets and bounds on problem sensitivity and robustness for conic linear optimization, Math. Program., 147 (2014), pp. 47-79, https://doi.org/10.1007/s10107-013-0709-1. · Zbl 1297.90121
[68] Model House Data Set, Visual Geometry Group, University of Oxford https://www.robots.ox.ac.uk/ vgg/data/mview/.
[69] H. Weyl, On the volume of tubes, Amer. J. Math., 2 (1939), pp. 461-472, https://doi.org/10.2307/2371513. · JFM 65.0796.01
[70] J. H. Wilkinson, Rounding Errors in Algebraic Processes, Prentice-Hall, Englewood Cliffs, NJ, 1963. · Zbl 1041.65502
[71] J. H. Wilkinson, The Algebraic Eigenvalue Problem, Oxford University Press, London, 1965. · Zbl 0258.65037
[72] H. Woźniakowski, Numerical stability for solving nonlinear equations, Numer. Math., 27 (1976), pp. 373-390, https://doi.org/10.1007/bf01399601. · Zbl 0336.65028
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.