##
**Low-rank inducing norms with optimality interpretations.**
*(English)*
Zbl 1414.90227

### MSC:

90C06 | Large-scale problems in mathematical programming |

90C25 | Convex programming |

90C26 | Nonconvex programming, global optimization |

90C46 | Optimality conditions and duality in mathematical programming |

90C59 | Approximation methods and heuristics in mathematical programming |

### Keywords:

low-rank optimization; low-rank inducing norms; regularization; matrix completion; semidefinite programming
PDF
BibTeX
XML
Cite

\textit{C. Grussler} and \textit{P. Giselsson}, SIAM J. Optim. 28, No. 4, 3057--3078 (2018; Zbl 1414.90227)

### References:

[1] | A. Antoulas, Approximation of Large-Scale Dynamical Systems, SIAM, Philadelphia, PA, 2005. · Zbl 1112.93002 |

[2] | A. C. Antoulas, On the approximation of Hankel matrices, in Operators, Systems and Linear Algebra: Three Decades of Algebraic Systems Theory, U. Helmke, ed., Vieweg+Teubner Verlag, Wiesbaden, 2013, pp. 17–22. |

[3] | F. Bach, R. Jenatton, J. Mairal, and G. Obozinski, Optimization with sparsity-inducing penalties, Found. Trends Mach. Learn., 4 (2012), pp. 1–106. · Zbl 06064248 |

[4] | E. J. Candès and Y. Plan, Matrix completion with noise, Proc. IEEE, 98 (2010), pp. 925–936. |

[5] | E. J. Candès and B. Recht, Exact matrix completion via convex optimization, Found. Comput. Math., 9 (2009), p. 717. |

[6] | V. Chandrasekaran, B. Recht, P. A. Parrilo, and A. S. Willsky, The convex geometry of linear inverse problems, Found. Comput. Math., 12 (2012), pp. 805–849. · Zbl 1280.52008 |

[7] | V. Chandrasekaran, S. Sanghavi, P. A. Parrilo, and A. S. Willsky, Rank-sparsity incoherence for matrix decomposition, SIAM J. Optim., 21 (2011), pp. 572–596. · Zbl 1226.90067 |

[8] | Y. Chen, M. R. Jovanović, and T. T. Georgiou, State covariances and the matrix completion problem, in Proceedings of the 52nd IEEE Conference on Decision and Control, Florence, Italy, IEEE, 2013, pp. 1702–1707. |

[9] | P. L. Combettes and J.-C. Pesquet, Proximal splitting methods in signal processing, in Fixed-Point Algorithms for Inverse Problems in Science and Engineering, H. Bauschke, R. Burachik, P. Combettes, V. Elser, D. Luke, H. Wolkowicz, eds., Springer, New York, 2011, pp. 185–212. · Zbl 1242.90160 |

[10] | X. V. Doan and S. Vavasis, Finding the largest low-rank clusters with Ky Fan 2-\(k\)-norm and \(ℓ_1\)-Norm, SIAM J. Optim., 26 (2016), pp. 274–312. · Zbl 1332.15032 |

[11] | A. Eriksson, T. T. Pham, T.-J. Chin, and I. Reid, The k-support norm and convex envelopes of cardinality and rank, in Proceedings of the 2015 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), IEEE, 2015, pp. 3349–3357. |

[12] | M. Fazel, Matrix Rank Minimization with Applications, Ph.D. thesis, Stanford University, Stanford, CA, 2002. |

[13] | M. Fazel, H. Hindi, and S. P. Boyd, A rank minimization heuristic with application to minimum order system approximation, in Proceedings of the 2001 American Control Conference, Vol. 6, IEEE, 2001, pp. 4734–4739. |

[14] | T. T. Georgiou, Spectral analysis based on the state covariance: the maximum entropy spectrum and linear fractional parametrization, IEEE Trans. Automat. Control, 47 (2002), pp. 1811–1823. · Zbl 1364.93799 |

[15] | T. T. Georgiou, The structure of state covariances and its relation to the power spectrum of the input, IEEE Trans. Automat. Control, 47 (2002), pp. 1056–1066. · Zbl 1364.93800 |

[16] | C. Grussler, LRINorm—A MATLAB Package for Rank Constrained Optimization by Low-Rank Inducing Norms and Non-Convex Proximal Splitting Methods, , 2018. |

[17] | C. Grussler, LRIPy—A Python Package for Rank Constrained Optimization by Low-Rank Inducing Norms and Non-Convex Proximal Splitting Methods, , 2018. |

[18] | C. Grussler and P. Giselsson, Efficient Proximal Mapping Computation for Unitarily Invariant Low-Rank Inducing Norms, preprint, , 2018. |

[19] | C. Grussler and P. Giselsson, Local convergence of proximal splitting methods for rank constrained problems, in Proceedings of the 2017 IEEE 56th Annual Conference on Decision and Control (CDC), IEEE, 2017, pp. 702–708. |

[20] | C. Grussler and A. Rantzer, On optimal low-rank approximation of non-negative matrices, in Proceedings of the 54th IEEE Conference on Decision and Control (CDC), IEEE, 2015, pp. 5278–5283. |

[21] | C. Grussler, A. Rantzer, and P. Giselsson, Low-rank optimization with convex constraints, IEEE Trans. Automat. Control, 63 (2018), pp. 4000–4007, . |

[22] | C. Grussler, A. Zare, M. R. Jovanović, and A. Rantzer, The use of the \(r⁎\) heuristic in covariance completion problems, in Proceedings of the 55th IEEE Conference on Decision and Control (CDC), IEEE, 2016. |

[23] | T. Hastie, R. Tibshirani, and M. Wainwright, Statistical Learning with Sparsity: The Lasso and Generalizations, CRC Press, Boca Raton, FL, 2015. · Zbl 1319.68003 |

[24] | J.-B. Hiriart-Urruty and C. Lemaréchal, Convex Analysis and Minimization Algorithms II: Advanced Theory and Bundle Methods, Grundlehren Math. Wiss., Springer, Berlin, Heidelberg, 1993. |

[25] | J.-B. Hiriart-Urruty and C. Lemaréchal, Convex Analysis and Minimization Algorithms I: Fundamentals, Grundlehren Math. Wiss., Springer, Berlin, Heidelberg, 1996. |

[26] | R. A. Horn and C. R. Johnson, Matrix Analysis, 2nd ed., Cambridge University Press, New York, NY, 2012. |

[27] | A. J. Izenman, Reduced-rank regression for the multivariate linear model, J. Multivariate Anal., 5 (1975), pp. 248–264. · Zbl 0313.62042 |

[28] | V. Larsson and C. Olsson, Convex low rank approximation, Int. J. Comput. Vis., 120 (2016), pp. 194–214. · Zbl 1398.68586 |

[29] | F. Lin, M. R. Jovanović, and T. T. Georgiou, An ADMM algorithm for matrix completion of partially known state covariances, in Proceedings of the 52nd IEEE Conference on Decision and Control, Florence, Italy, IEEE, 2013, pp. 1684–1689. |

[30] | A. M. McDonald, M. Pontil, and D. Stamos, New Perspectives on k-Support and Cluster Norms, preprint, , 2015. · Zbl 1392.68356 |

[31] | N. Parikh and S. Boyd, Proximal Algorithms, Found. Trends Optim., 1, Now Publishers, Hanover, MA, 2014, pp. 127–239. |

[32] | D. Peaucelle, D. Henrion, Y. Labit, and K. Taitz, User’s Guide for SEDUM Interface 1.04, LAAS-CNRS, Toulouse, 2002. |

[33] | B. Recht, M. Fazel, and P. A. Parrilo, Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization, SIAM Rev., 52 (2010), pp. 471–501. · Zbl 1198.90321 |

[34] | G. C. Reinsel and R. Velu, Multivariate Reduced-Rank Regression: Theory and Applications, Lect. Notes Stat. 136, Springer, New York, 1998. · Zbl 0909.62066 |

[35] | R. T. Rockafellar, Convex Analysis, Princeton University Press, Princeton, NJ, 1970. · Zbl 0193.18401 |

[36] | G. W. Stewart and J.-G. Sun, Matrix Perturbation Theory, Academic Press, New York, 1990. · Zbl 0706.65013 |

[37] | K. C. Toh, R. H. Tutuncu, and M. J. Todd, On the implementation of SDPT3 (version 3.1)—A MATLAB software package for semidefinite-quadratic-linear programming, in Proceedings of the IEEE International Conference on Robotics and Automation, New Orleans, LA, IEEE, 2004, pp. 290–296. |

[38] | R. Vidal, Y. Ma, and S. S. Sastry, Generalized Principal Component Analysis, Interdiscip. Appl. Math. 40, Springer-Verlag, New York, 2016. · Zbl 1349.62006 |

[39] | G. Watson, Characterization of the subdifferential of some matrix norms, Linear Algebra Appl., 170 (1992), pp. 33–45. · Zbl 0751.15011 |

[40] | A. Zare, Y. Chen, M. R. Jovanović, and T. T. Georgiou, Low-complexity modeling of partially available second-order statistics: Theory and an efficient matrix completion algorithm, IEEE Trans. Automat. Control, 62 (2017), pp. 1368–1383, . · Zbl 1366.62112 |

[41] | A. Zare, M. R. Jovanović, and T. T. Georgiou, Alternating direction optimization algorithms for covariance completion problems, in Proceedings of the 2015 American Control Conference (ACC), Chicago, IL, IEEE, 2015, pp. 515–520. |

[42] | A. Zare, M. R. Jovanović, and T. T. Georgiou, Colour of turbulence, J. Fluid Mech., 812 (2017), pp. 636–680, . · Zbl 1383.76303 |

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.