Share This Article:

Low-Rank Positive Approximants of Symmetric Matrices

Abstract Full-Text HTML Download Download as PDF (Size:2572KB) PP. 172-185
DOI: 10.4236/alamt.2014.43015    2,107 Downloads   2,762 Views   Citations
Author(s)    Leave a comment

ABSTRACT

Given a symmetric matrix X, we consider the problem of finding a low-rank positive approximant of X. That is, a symmetric positive semidefinite matrix, S, whose rank is smaller than a given positive integer, , which is nearest to X in a certain matrix norm. The problem is first solved with regard to four common norms: The Frobenius norm, the Schatten p-norm, the trace norm, and the spectral norm. Then the solution is extended to any unitarily invariant matrix norm. The proof is based on a subtle combination of Ky Fan dominance theorem, a modified pinching principle, and Mirsky minimum-norm theorem.

Conflicts of Interest

The authors declare no conflicts of interest.

Cite this paper

Dax, A. (2014) Low-Rank Positive Approximants of Symmetric Matrices. Advances in Linear Algebra & Matrix Theory, 4, 172-185. doi: 10.4236/alamt.2014.43015.

References

[1] Dax, A. (2014) Imputing Missing Entries of a Data Matrix: A Review. Techical Report, Hydrological Service of Israel.
[2] Trosset, M.W. (2000) Distance Matrix Completion by Numerical Optimization. Computational Optimization and Applications, 17, 11-22.
http://dx.doi.org/10.1023/A:1008722907820
[3] Higham, N.J. (1988) Computing a Nearest Symmetric Positive Semidefinite Matrix. Linear Algebra and Its Applications, 103, 103-118.
http://dx.doi.org/10.1016/0024-3795(88)90223-6
[4] Halmos, P.R. (1972) Positive Approximants of Operators. Indiana University Mathematics Journal, 21, 951-960.
http://dx.doi.org/10.1512/iumj.1972.21.21076
[5] Rogers, D.D. and Ward, J.D. (1981) Cp-Minimal Positive Approximants. Acta Scientiarum Mathematicarum, 43, 109-115.
[6] Ando, T. (1985) Approximation in Trace Norm by Positive Semidefinite Matrices. Linear Algebra and Its Applications, 71, 15-21.
http://dx.doi.org/10.1016/0024-3795(85)90230-7
[7] Ando, T., Sekiguchi, T. and Suzuki, T. (1973) Approximation by Positive Operators. Mathematische Zeitschrift, 131, 273-282.
http://dx.doi.org/10.1007/BF01174903
[8] Bhatia, R. (1997) Matrix Analysis. Springer, New York.
http://dx.doi.org/10.1007/978-1-4612-0653-8
[9] Bhatia, R. and Kittaneh, F. (1992) Approximation by Positive Operators. Linear Algebra and Its Applications, 161, 1-9.
http://dx.doi.org/10.1016/0024-3795(92)90001-Q
[10] Bouldin, R. (1973) Positive Approximants. Transactions of the American Mathematical Society, 177, 391-403. http://dx.doi.org/10.1090/S0002-9947-1973-0317082-6
[11] Sekiguchi, T. (1976) Positive Approximants of Normal Operators. Hokkaido Mathematical Journal, 5, 270-279.
http://dx.doi.org/10.14492/hokmj/1381758677
[12] Bouldin, R. (1980) Best Approximation of a Normal Operator in the Schatten p-Norm. Proceedings of the American Mathematical Society, 80, 277-282.
[13] Bouldin, R. (1987) Best Approximation of a Normal Operator in the Trace Norm. Acta Scientiarum Mathematicarum, 51, 467-474.
[14] Bouldin, R., (1988) Best Approximation of a Nonnormal Operator in the Trace Norm. Journal of Mathematical Analysis and Applications, 132, 102-113.
http://dx.doi.org/10.1016/0022-247X(88)90046-7
[15] Laszkiewicz, B. and Zietak, K. (2008) Approximation by Matrices with Restricted Spectra. Linear Algebra and Its Applications, 428, 1031-1040.
http://dx.doi.org/10.1016/j.laa.2007.09.009
[16] Phillips, J. (1977) Nearest Normal Approximation for Certain Normal Operators. Proceedings of the American Mathematical Society, 67, 236-240.
http://dx.doi.org/10.1090/S0002-9939-1977-0458212-4
[17] Ruhe, A. (1987) Closest Normal Matrix Finally Found! BIT Numerical Mathematics, 27, 585-598.
http://dx.doi.org/10.1007/BF01937278
[18] Zietak, K. (1997) Strict Spectral Approximation of a Matrix and Some Related Problems. Applicationes Mathematicae, 24, 267-280.
[19] Higham, N.J. (1989) Matrix Nearness Problems and Applications. In: Gover, M.J.C. and Barnett, S., Eds., Applications of Matrix Theory, Oxford University Press, Oxford, 1-27.
[20] Fan, K. (1951) Maximum Properties and Inequalities for the Eigenvalues of Completely Continuous Operators. Proceedings of the National Academy of Sciences of the United States of America, 37, 760-766.
http://dx.doi.org/10.1073/pnas.37.11.760
[21] Fan, K. and Hoffman, A.J. (1955) Some Metric Inequalities in the Space of Matrices. Proceedings of the American Mathematical Society, 6, 111-116.
http://dx.doi.org/10.1090/S0002-9939-1955-0067841-7
[22] Horn, R.A. and Johnson, C.R. (1991) Topics in Matrix Analysis. Cambridge University Press, Cambridge.
http://dx.doi.org/10.1017/CBO9780511840371
[23] Marshall, A.W., Olkin, I. and Arnold, B.C. (2011) Inequalities: Theory of Majorization and Its Applications. Springer Series in Statistics, 2nd Edition, Springer, New York.
[24] Zhang, F. (1999) Matrix Theory: Basic Results and Techniques. Springer-Verlag, New York.
http://dx.doi.org/10.1007/978-1-4757-5797-2
[25] Dax, A. (2010) On Extremum Properties of Orthogonal Quotient Matrices. Linear Algebra and Its Applications, 432, 1234-1257.
http://dx.doi.org/10.1016/j.laa.2009.10.034
[26] Eckart, C. and Young, G. (1936) The Approximation of One Matrix by Another of Lower Rank. Psychometrika, 1, 211-218.
http://dx.doi.org/10.1007/BF02288367
[27] Mirsky, L. (1960) Symmetric Gauge Functions and Unitarily Invariant Norms. Quarterly Journal of Mathematics, 11, 50-59.
http://dx.doi.org/10.1093/qmath/11.1.50

  
comments powered by Disqus

Copyright © 2019 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.