Low-rank matrix approximations over canonical subspaces
Keywords:Canonical subspaces, Low-rank positive approximants, The nearest rank-k centered matrix, The nearest source matrix
AbstractIn this paper we derive closed form expressions for the nearest rank-\(k\) matrix on canonical subspaces. We start by studying three kinds of subspaces. Let \(X\) and \(Y\) be a pair of given matrices. The first subspace contains all the \(m\times n\) matrices \(A\) that satisfy \(AX=O\). The second subspace contains all the \(m \times n\) matrices \(A\) that satisfy \(Y^TA = O\), while the matrices in the third subspace satisfy both \(AX =O\) and \(Y^TA = 0\). The second part of the paper considers a subspace that contains all the symmetric matrices \(S\) that satisfy \(SX =O\). In this case, in addition to the nearest rank-\(k\) matrix we also provide the nearest rank-\(k\) positive approximant on that subspace. A further insight is gained by showing that the related cones of positive semidefinite matrices, and negative semidefinite matrices, constitute a polar decomposition of this subspace. The paper ends with two examples of applications. The first one regards the problem of computing the nearest rank-\(k\) centered matrix, and adds new insight into the PCA of a matrix. The second application comes from the field of Euclidean distance matrices. The new results on low-rank positive approximants are used to derive an explicit expression for the nearest source matrix. This opens a direct way for computing the related positions matrix.
H. Abdi and L.J. Williams, Principal Component Analysis, Wiley Interdisciplinary Reviews: Computational Statistics 2(2010), pp. 433–459, https://doi.org/10.1002/wics.101 DOI: https://doi.org/10.1002/wics.101
T. Ando, Approximation in trace norm by positive semidefinite matrices, Linear Algebra and its Applications 71 (1985), pp. 15–21, https://doi.org/10.1016/0024-3795(85)90230-7 DOI: https://doi.org/10.1016/0024-3795(85)90230-7
D.P. Bertsekas, Convex optimization theory, Athena Scientific, 2009.
R. Bhatia, Matrix Analysis, Springer, New York, 1997. DOI: https://doi.org/10.1007/978-1-4612-0653-8
R. Bhatia and F. Kittaneh, Approximation by positive operators, Linear Algebra Appl. 161 (1992), pp. 1–9, https://doi.org/10.1016/0024-3795(92)90001-q DOI: https://doi.org/10.1016/0024-3795(92)90001-Q
I. Borg and P.J.F. Groenen, Modern multidimensional scaling: Theory and applications (2nd ed.), Springer Series in Statistics, Springer, 2005.
D.I. Chu, H.C. Brown and M.T. Chu, On least squares Euclidean distance matrix approximation and completion, Dept. of Mathematics, North Carolina State University,Tech. Rep., 2003.
T.F. Cox and M.A.A. Cox, Multidimensional Scaling, 2nd Ed., Chapman and Hall / CRC, 2001. DOI: https://doi.org/10.1201/9781420036121
G. Crippen and T. Havel, Distance Geometry and Molecular Conformation, Wiley, New York, 1988.
J. Dattorro, Convex optimization and Euclidean distance geometry, Meboo Publishing, USA, 2005.
A. Dax, On extremum properties of orthogonal quotient matrices, Linear Algebra Appl. 432 (2010), pp. 1234–1257, https://doi.org/10.1016/j.laa.2009.10.034 DOI: https://doi.org/10.1016/j.laa.2009.10.034
A. Dax, Low-rank positive approximants of symmetric matrices, Advances in LinearAlgebra & Matrix Theory 4 (2014), pp. 172–185, https://doi.org/10.4236/alamt.2014.43015 DOI: https://doi.org/10.4236/alamt.2014.43015
Ky Fan, Maximum properties and inequalities for the eigenvalues of completely continuous operators, Proc. Nat. Acad. Sci, USA 37(1951), pp. 760–766, https://doi.org/10.1073/pnas.37.11.760 DOI: https://doi.org/10.1073/pnas.37.11.760
Ky Fan and A.J. Hoffman, Some metric inequalities in the space of matrices, Proc. Amer. Math. Soc. 6 (1955), pp. 111–116, https://doi.org/10.1090/s0002-9939-1955-0067841-7 DOI: https://doi.org/10.1090/S0002-9939-1955-0067841-7
W. Glunt, T.L. Hayden, S. Hong and J. Wells, An alternating projection algorithm for computing the nearest Euclidean distance matrix, SIAM J. Matrix Anal. Appl. 11(1990), pp. 589–600, https://doi.org/10.1137/0611042 DOI: https://doi.org/10.1137/0611042
W. Glunt, T.L. Hayden and R. Raydan, Molecular conformations from distance matrices, J. Computational Chemistry 14 (1993), pp. 114–120, https://doi.org/10.1002/jcc.540140115 DOI: https://doi.org/10.1002/jcc.540140115
T.L. Hayden and J. Wells, Approximation by matrices positive semidefinite on a subspace, Linear Algebra Appl. 109 (1988), pp. 115–130, https://doi.org/10.1016/0024-3795(88)90202-9 DOI: https://doi.org/10.1016/0024-3795(88)90202-9
N.J. Higham, Computing a nearest symmetric positive semidefinite matrix, Linear Algebra and Appl. 103 (1988), pp. 103–118, https://doi.org/10.1016/0024-3795(88)90223-6 DOI: https://doi.org/10.1016/0024-3795(88)90223-6
N.J. Higham, Matrix nearness problems and applications, in M.J.C. Gover and S. Barnett, editors, Applications of Matrix Theory, pp. 1–27. Oxford University Press, 1989.
N. Krislock and H. Wolkowicz, Explicit sensor network localization using semidefinite representations and facial reductions, SIAM J. Optim. 20 (2010), pp. 2679–2708, https://doi.org/10.1137/090759392 DOI: https://doi.org/10.1137/090759392
N. Krislock and H. Wolkowicz, Euclidean distance matrices and applications, In Handbook of Semidefinite, Cone and Polynomial Optimization, M. Anjos and J.Lasserre (Eds.), 2010. DOI: https://doi.org/10.1007/978-1-4614-0769-0_30
R. Mathar, The best Euclidean fit to a given distance matrix in prescribed dimensions, Linear Algebra and its Applications 67 (1985), pp. 1–6, https://doi.org/10.1016/0024-3795(85)90181-8 DOI: https://doi.org/10.1016/0024-3795(85)90181-8
L. Mirsky, Symmetric Gauge Functions and Unitarily Invariant Norms, Quarterly Journal of Mathematics 11 (1960), pp. 50–59, https://doi.org/10.1093/qmath/11.1.50 DOI: https://doi.org/10.1093/qmath/11.1.50
J.J. Moreau, Decomposition orthogonal d’un espace hilbertien selon deux cones mutuellement polaires, C.R. Acad. Sci. Paris 255 (1962), pp. 238–240.
D.D. Rogers and J.D. Ward, Cp-minimal positive approximants, Acta Sci. Math. 43 (1981), pp. 109–115
How to Cite
Copyright (c) 2020 Journal of Numerical Analysis and Approximation Theory
This work is licensed under a Creative Commons Attribution 4.0 International License.
Open Access. This article is distributed under the terms of the Creative Commons Attribution 4.0 International License, which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.