ALAMT  Vol.4 No.3 , September 2014
Low-Rank Positive Approximants of Symmetric Matrices
Author(s) Achiya Dax
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.

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

 
 
Top