research-article

The minimum-rank gram matrix completion via modified fixed point continuation method

Authors:

Lihong ZhiAuthors Info & Claims

ISSAC '11: Proceedings of the 36th international symposium on Symbolic and algebraic computation

Pages 241 - 248

https://doi.org/10.1145/1993886.1993924

Published: 08 June 2011 Publication History

Abstract

The problem of computing a representation for a real polynomial as a sum of minimum number of squares of polynomials can be casted as finding a symmetric positive semidefinite real matrix of minimum rank subject to linear equality constraints. In this paper, we propose algorithms for solving the minimum-rank Gram matrix completion problem, and show the convergence of these algorithms. Our methods are based on the fixed point continuation method. We also use the Barzilai-Borwein technique and a specific linear combination of two previous iterates to accelerate the convergence of modified fixed point continuation algorithms. We demonstrate the effectiveness of our algorithms for computing approximate and exact rational sum of squares decompositions of polynomials with rational coefficients.

References

[1]

Barrett, W., Johnson, C. R., and Tarazaga, P. The real positive definite completion problem for a simple cycle. Linear Algebra Appl. 192 (1993), 3--31.

[2]

Barzilai, J., and Borwein, J. Two-point step size gradient methods. IMA J. Numer. Anal. 8 (1988), 141--148.

[3]

Beck, A., and Teboulle, M. A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J. Imaging Sci. 2, 1 (2009), 183--202.

Digital Library

[4]

Burer, S., and Monteiro, R. A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization. Math. Program. 95, 2 (2003), 329--357.

[5]

Burer, S., and Monteiro, R. Local minima and convergence in low-rank semidefinite programming. Math. Program. 103, 3 (2005), 427--444.

Digital Library

[6]

Cai, J.-F., Candès, E. J., and Shen, Z. A singular value thresholding algorithm for matrix completion. SIAM J. Optim. 20, 4 (2010), 1956--1982.

Digital Library

[7]

Candès, E. J., and Recht, B. Exact matrix completion via convex optimization. Found. Comput. Math. 9, 6 (2009), 717--772.

Digital Library

[8]

Candès, E. J., and Tao, T. The power of convex relaxation: near-optimal matrix completion. IEEE Trans. Inform. Theory 56, 5 (2010), 2053--2080.

Digital Library

[9]

Chistov, A., and Grigoriev, D. Complexity of quantifier elimination in the theory of algebraically closed fields. In Proceedings of the Mathematical Foundations of Computer Science 1984 (London, UK, 1984), Springer-Verlag, pp. 17--31.

Digital Library

[10]

Choi, M., Lam, T., and Reznick, B. Sums of squares of real polynomials. Symp. in Pure Math. 58, 2 (1995), 103--126.

[11]

de Klerk, E., Roos, C., and Terlaky, T. Initialization in semidefinite programming via a self-dual skew-symmetric embedding. Oper. Res. Lett. 20, 5 (1997), 213--221.

Digital Library

[12]

Fazel, M. Matrix rank minimization with applications. PhD thesis, Stanford University, 2002.

[13]

Fazel, M., Hindi, H., and Boyd, S. A rank minimization heuristic with application to minimum order system approximation. In Proceedings of the 2001 American Control Conference (2001), pp. 4734--4739.

[14]

Goldfarb, D., and Ma, S. Convergence of fixed point continuation algorithms for matrix rank minimization. Foundations of Computational Mathematics 11, 2 (2011), 183--210.

Digital Library

[15]

Golub, G. H., and Van Loan, C. F. Matrix computations, third ed. Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, Baltimore, MD, 1996.

Digital Library

[16]

Grone, R., Johnson, C. R., de Sá, E. M., and Wolkowicz, H. Positive definite completions of partial Hermitian matrices. Linear Algebra Appl. 58 (1984), 109--124.

[17]

Hale, E. T., Yin, W., and Zhang, Y. Fixed-point continuation for $l_1$-minimization: methodology and convergence. SIAM J. Optim. 19, 3 (2008), 1107--1130.

Digital Library

[18]

Henrion, D., and Malick, J. Projection methods in convex optimization. LAAS-CNRS Research Report 10730 (2010).

[19]

Henrion, D., and Malick, J. Projection methods for conic feasibility problems; application to sum-of-squares decompositions. Optimization Methods and Software 26, 1 (2011), 23--46.

Digital Library

[20]

Ji, S., and Ye, J. An accelerated gradient method for trace norm minimization. In Proceedings of the 26th Annual International Conference on Machine Learning (New York, NY, USA, 2009), ICML '09, ACM, pp. 457--464.

Digital Library

[21]

Kaltofen, E., Li, B., Yang, Z., and Zhi, L. Exact certification of global optimality of approximate factorizations via rationalizing sums-of-squares with floating point scalars. In ISSAC '08: Proceedings of the twenty-first international symposium on Symbolic and algebraic computation (New York, NY, USA, 2008), ACM, pp. 155--164.

Digital Library

[22]

Kaltofen, E., Li, B., Yang, Z., and Zhi, L. Exact certification in global polynomial optimization via sums-of-squares of rational functions with rational coefficients, 2009. Accepted for publication in J. Symbolic Comput.

Digital Library

[23]

Kocvara, M., and Stingl, M. On the solution of large-scale SDP problems by the modified barrier method using iterative solvers. Math. Program. 109, 2--3, Ser. B (2007), 413--444.

Digital Library

[24]

Larsen, R. PROPACK - software for large and sparse SVD calculations. Available from: http://soi.stanford.edu/ rmunk/PROPACK/.

[25]

Laurent, M. The real positive semidefinite completion problem for series-parallel graphs. Linear Algebra Appl. 252 (1997), 347--366.

[26]

Laurent, M. Polynomial instances of the positive semidefinite and Euclidean distance matrix completion problems. SIAM J. Matrix Anal. Appl. 22, 3 (2000), 874--894.

Digital Library

[27]

Laurent, M. Matrix completion problems. Encyclopedia of Optimization III (Interior - M) (2001), 221--229.

[28]

Lewis, A. S. Convex analysis on the Hermitian matrices. SIAM J. Optim. 6, 1 (1996), 164--177.

Digital Library

[29]

Liu, Z., and Vandenberghe, L. Interior-point method for nuclear norm approximation with application to system identification. SIAM J. Matrix Anal. Appl. 31 (2009), 1235--1256.

Digital Library

[30]

Löfberg, J. YALMIP : A toolbox for modeling and optimization in MATLAB. In Proc. IEEE CCA/ISIC/CACSD Conf. (Taipei, Taiwan, 2004). URL: http://control.ee.ethz.ch/ joloef/yalmip.php.

[31]

Ma, S., Goldfarb, D., and Chen, L. Fixed point and bregman iterative methods for matrix rank minimization. Math. Program. (2009), 1--33.

[32]

Ma, Y. The minimum-rank Gram matrix completion via fixed point continuation method (in Chinese). Journal of Systems Science and Mathematical Sciences 30, 11 (2010), 1501--1511.

[33]

Malick, J., Povh, J., Rendl, F., and Wiegele, A. Regularization methods for semidefinite programming. SIAM J. Optim. 20, 1 (2009), 336--356.

Digital Library

[34]

Nesterov, Y. A method of solving a convex programming problem with convergence rate $O(1/k^2)$. Soviet Mathematics Doklady 27 (1983), 372--376.

[35]

Nesterov, Y. Smooth minimization of non-smooth functions. Math. Program. 103, 1 (2005), 127--152.

Digital Library

[36]

Nesterov, Y. Gradient methods for minimizing composite objective function. Tech. rep., 2007.

[37]

Nie, J. Regularization methods for sum of squares relaxations in large scale polynomial optimization. Tech. rep., 2009. Available: http://arxiv.org/abs/0909.3551.

[38]

Peyrl, H., and Parrilo, P. A Macaulay 2 package for computing sum of squares decompositions of polynomials with rational coefficients. In ProcSNC07 (2007), pp. 207--208.

Digital Library

[39]

Peyrl, H., and Parrilo, P. Computing sum of squares decompositions with rational coefficients. Theoretical Computer Science 409 (2008), 269--281.

Digital Library

[40]

Pfister, A. Zur Darstellung definiter Funktionen als Summe von Quadraten. Inventiones Math. 4, 4 (1967), 229--236.

[41]

Pourchet, Y. Sur la représentation en somme de carrés des polynômes à une indéterminée sur un corps de nombres algébriques. Acta Arith. 19 (1971), 89--104.

[42]

Powers, V., and Wörmann, T. An algorithm for sums of squares of real polynomials. J. Pure Appl. Algebra 127, 1 (1998), 99--104.

[43]

Recht, B., Fazel, M., and Parrilo, P. A. Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. SIAM Rev. 52, 3 (2010), 471--501.

Digital Library

[44]

Recht, B., Xu, W., and Hassibi, B. Necessary and sufficient conditions for success of the nuclear norm heuristic for rank minimization. In CDC (2008), pp. 3065--3070.

[45]

Rennie, J., and Srebro, N. Fast maximum margin matrix factorization for collaborative prediction. In Proceedings of the 22nd international conference on Machine learning (2005), ICML '05, pp. 713--719.

Digital Library

[46]

Rockafellar, R. Convex Analysis. Princeton University Press, 1972.

[47]

Srebro, N., Rennie, J., and Jaakkola, T. Maximum-margin matrix factorization. In Advances in Neural Information Processing Systems (2005).

[48]

Sturm, J. Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones. Optimization Methods and Software 11/12 (1999), 625--653.

[49]

Toh, K.-C., and Yun, S. An accelerated proximal gradient algorithm for nuclear norm regularized linear least squares problems. Tech. rep., 2009. Available: http://www.optimization-online.org/DB HTML/2009/03/2268.html.

[50]

Tseng, P. On accelerated proximal gradient methods for convex-concave optimization. Submitted to SIAM J. Optim (2008).

[51]

Watson, G. A. Characterization of the subdifferential of some matrix norms. Linear Algebra Appl. 170 (1992), 33--45.

[52]

Wen, Z., Yin, W., Goldfarb, D., and Zhang, Y. A fast algorithm for sparse reconstruction based on shrinkage, subspace optimization, and continuation. SIAM J. Sci. Comput. 32, 4 (2010), 1832--1857.

Digital Library

[53]

Zhao, X.-Y., Sun, D., and Toh, K.-C. A Newton-CG augmented Lagrangian method for semidefinite programming. SIAM J. Optim. 20, 4 (2010), 1737--1765.

Digital Library

Cited By

Han RWang SFu SLi YLiu SZhou W(2020)Image Inpainting by Low-Rank Prior and Iterative DenoisingIEEE Access10.1109/ACCESS.2020.30072048(123310-123319)Online publication date: 2020
https://doi.org/10.1109/ACCESS.2020.3007204
Shang FJiao LLiu YTong H(2013)Semi-supervised learning with nuclear norm regularizationPattern Recognition10.1016/j.patcog.2013.01.00946:8(2323-2336)Online publication date: 1-Aug-2013
https://dl.acm.org/doi/10.1016/j.patcog.2013.01.009
Ma YZhi Lvan der Hoeven Jvan Hoeij M(2012)Computing real solutions of polynomial systems via low-rank moment matrix completionProceedings of the 37th International Symposium on Symbolic and Algebraic Computation10.1145/2442829.2442866(249-256)Online publication date: 22-Jul-2012
https://dl.acm.org/doi/10.1145/2442829.2442866
Show More Cited By

Index Terms

The minimum-rank gram matrix completion via modified fixed point continuation method

Recommendations

Fixed point and Bregman iterative methods for matrix rank minimization

The linearly constrained matrix rank minimization problem is widely applicable in many fields such as control, signal processing and system identification. The tightest convex relaxation of this problem is the linearly constrained nuclear norm ...
A fast tri-factorization method for low-rank matrix recovery and completion

In recent years, matrix rank minimization problems have received a significant amount of attention in machine learning, data mining and computer vision communities. And these problems can be solved by a convex relaxation of the rank minimization problem ...
Fast and Accurate Matrix Completion via Truncated Nuclear Norm Regularization

Recovering a large matrix from a small subset of its entries is a challenging problem arising in many real applications, such as image inpainting and recommender systems. Many existing approaches formulate this problem as a general low-rank matrix ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ISSAC '11: Proceedings of the 36th international symposium on Symbolic and algebraic computation

June 2011

372 pages

ISBN:9781450306751

DOI:10.1145/1993886

General Chair:
Éric Schost
The University of Western Ontario, Canada
,
Program Chair:
Ioannis Z. Emiris
University of Athens, Greece

Copyright © 2011 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGSAM: ACM Special Interest Group on Symbolic and Algebraic Manipulation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 June 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ISSAC '11

Sponsor:

SIGSAM

ISSAC '11: International Symposium on Symbolic and Algebraic Computation

June 8 - 11, 2011

California, San Jose, USA

Acceptance Rates

Overall Acceptance Rate 395 of 838 submissions, 47%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
127
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Han RWang SFu SLi YLiu SZhou W(2020)Image Inpainting by Low-Rank Prior and Iterative DenoisingIEEE Access10.1109/ACCESS.2020.30072048(123310-123319)Online publication date: 2020
https://doi.org/10.1109/ACCESS.2020.3007204
Shang FJiao LLiu YTong H(2013)Semi-supervised learning with nuclear norm regularizationPattern Recognition10.1016/j.patcog.2013.01.00946:8(2323-2336)Online publication date: 1-Aug-2013
https://dl.acm.org/doi/10.1016/j.patcog.2013.01.009
Ma YZhi Lvan der Hoeven Jvan Hoeij M(2012)Computing real solutions of polynomial systems via low-rank moment matrix completionProceedings of the 37th International Symposium on Symbolic and Algebraic Computation10.1145/2442829.2442866(249-256)Online publication date: 22-Jul-2012
https://dl.acm.org/doi/10.1145/2442829.2442866
Shang FJiao LWang FYang QAgarwal DPei J(2012)Semi-supervised learning with mixed knowledge informationProceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining10.1145/2339530.2339646(732-740)Online publication date: 12-Aug-2012
https://dl.acm.org/doi/10.1145/2339530.2339646

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents