{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,18]],"date-time":"2026-09-18T08:53:53Z","timestamp":1789721633031,"version":"4.0.1"},"reference-count":42,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","funder":[{"DOI":"10.13039\/501100001729","name":"Stiftelson f\u00c3\u00b6r Strategisk Forskning","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001729","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004359","name":"Vetenskapsr\u00e5det","doi-asserted-by":"publisher","award":["621-2012-5357"],"award-info":[{"award-number":["621-2012-5357"]}],"id":[{"id":"10.13039\/501100004359","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Optim."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>Optimization problems with rank constraints appear in many diverse fields such as control, machine learning, and image analysis. Since the rank constraint is nonconvex, these problems are often approximately solved via convex relaxations. Nuclear norm regularization is the prevailing convexifying technique for dealing with these types of problem. This paper introduces a family of low-rank inducing norms and regularizers which include the nuclear norm as a special case. A posteriori guarantees on solving an underlying rank constrained optimization problem with these convex relaxations are provided. We evaluate the performance of the low-rank inducing norms on three matrix completion problems. In all examples, the nuclear norm heuristic is outperformed by convex relaxations based on other low-rank inducing norms. For two of the problems there exist low-rank inducing norms that succeed in recovering the partially unknown matrix, while the nuclear norm fails. These low-rank inducing norms are shown to be representable as semidefinite programs. Moreover, these norms have cheaply computable proximal mappings, which make it possible to also solve problems of large size using first-order methods.<\/jats:p>","DOI":"10.1137\/17m1115770","type":"journal-article","created":{"date-parts":[[2018,11,1]],"date-time":"2018-11-01T12:20:09Z","timestamp":1541074809000},"page":"3057-3078","source":"Crossref","is-referenced-by-count":9,"title":["Low-Rank Inducing Norms with Optimality Interpretations"],"prefix":"10.1137","volume":"28","author":[{"given":"Christian","family":"Grussler","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pontus","family":"Giselsson","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,11,1]]},"reference":[{"key":"atypb1","doi-asserted-by":"crossref","unstructured":"A. Antoulas,\n                      Approximation of Large-Scale Dynamical Systems\n                      , SIAM, Philadelphia, PA, 2005.","DOI":"10.1137\/1.9780898718713"},{"key":"atypb2","first-page":"17","author":"Antoulas A. C.","year":"2013","journal-title":"Wiesbaden"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1561\/2200000015"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2009.2035722"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-009-9045-5"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-012-9135-7"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1137\/090761793"},{"key":"atypb8","first-page":"1702","author":"Chen Y.","year":"2013","journal-title":"Italy, IEEE"},{"key":"atypb9","first-page":"185","author":"Combettes P. L.","year":"2011","journal-title":"New York"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1137\/140962097"},{"key":"atypb11","first-page":"3349","author":"Eriksson A.","year":"2015","journal-title":"IEEE"},{"key":"atypb12","unstructured":"M. Fazel,\n                      Matrix Rank Minimization with Applications\n                      , Ph.D. thesis, Stanford University, Stanford, CA, 2002."},{"key":"atypb13","first-page":"4734","author":"Fazel M.","year":"2001","journal-title":"IEEE"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2002.804482"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2002.800643"},{"key":"atypb16","unstructured":"C. Grussler,\n                      LRINorm-A MATLAB Package for Rank Constrained Optimization by Low-Rank Inducing Norms and Non-Convex Proximal Splitting Methods\n                      ,https:\/\/github.com\/LowRankOpt\/LRINorm, 2018."},{"key":"atypb17","unstructured":"C. Grussler,\n                      LRIPy-A Python Package for Rank Constrained Optimization by Low-Rank Inducing Norms and Non-Convex Proximal Splitting Methods\n                      ,https:\/\/github.com\/LowRankOpt\/LRIPy, 2018."},{"key":"atypb18","unstructured":"C. Grussler and P. Giselsson,\n                      Efficient Proximal Mapping Computation for Unitarily Invariant Low-Rank Inducing Norms\n                      , preprint,arXiv:1810:07570, 2018."},{"key":"atypb19","first-page":"702","author":"Grussler C.","year":"2017","journal-title":"IEEE"},{"key":"atypb20","first-page":"5278","author":"Grussler C.","year":"2015","journal-title":"IEEE"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2018.2813009"},{"key":"atypb22","doi-asserted-by":"crossref","unstructured":"C. Grussler, A. Zare, M. R. Jovanovi\u0107, and A. Rantzer,\n                      The use of the $r\\ast$ heuristic in covariance completion problems\n                      , in Proceedings of the 55th IEEE Conference on Decision and Control (CDC), IEEE, 2016.","DOI":"10.1109\/CDC.2016.7798554"},{"key":"atypb23","doi-asserted-by":"crossref","unstructured":"T. Hastie, R. Tibshirani, and M. Wainwright,\n                      Statistical Learning with Sparsity: The Lasso and Generalizations\n                      , CRC Press, Boca Raton, FL, 2015.","DOI":"10.1201\/b18401"},{"key":"atypb24","doi-asserted-by":"crossref","unstructured":"J.B. Hiriart-Urruty and C. Lemar\u00e9chal,\n                      Convex Analysis and Minimization Algorithms II: Advanced Theory and Bundle Methods\n                      , Grundlehren Math. Wiss., Springer, Berlin, Heidelberg, 1993.","DOI":"10.1007\/978-3-662-06409-2"},{"key":"atypb25","unstructured":"J.B. Hiriart-Urruty and C. Lemar\u00e9chal,\n                      Convex Analysis and Minimization Algorithms I: Fundamentals\n                      , Grundlehren Math. Wiss., Springer, Berlin, Heidelberg, 1996."},{"key":"atypb26","unstructured":"R. A. Horn and C. R. Johnson,\n                      Matrix Analysis\n                      , 2nd ed., Cambridge University Press, New York, NY, 2012."},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1016\/0047-259X(75)90042-1"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1007\/s11263-016-0904-7"},{"key":"atypb29","first-page":"1684","author":"Lin F.","year":"2013","journal-title":"Italy, IEEE"},{"key":"atypb30","unstructured":"A. M. McDonald, M. Pontil, and D. Stamos,\n                      New Perspectives on k-Support and Cluster Norms\n                      , preprint,arXiv:1512.08204, 2015."},{"key":"atypb31","first-page":"127","author":"Parikh N.","year":"2014","journal-title":"MA"},{"key":"atypb32","unstructured":"D. Peaucelle, D. Henrion, Y. Labit, and K. Taitz,\n                      User's Guide for SEDUM Interface\n                      1.04, LAAS-CNRS, Toulouse, 2002."},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1137\/070697835"},{"key":"atypb34","doi-asserted-by":"crossref","unstructured":"G. C. Reinsel and R. Velu,\n                      Multivariate Reduced-Rank Regression: Theory and Applications\n                      , Lect. Notes Stat. 136, Springer, New York, 1998.","DOI":"10.1007\/978-1-4757-2853-8"},{"key":"atypb35","unstructured":"R. T. Rockafellar,\n                      Convex Analysis\n                      , Princeton University Press, Princeton, NJ, 1970."},{"key":"atypb36","unstructured":"G. W. Stewart and J.G. Sun,\n                      Matrix Perturbation Theory\n                      , Academic Press, New York, 1990."},{"key":"atypb37","first-page":"290","author":"Toh K. C.","year":"2004","journal-title":"Proceedings of the IEEE International Conference on Robotics and Automation, New Orleans, LA, IEEE"},{"key":"atypb38","doi-asserted-by":"crossref","unstructured":"R. Vidal, Y. Ma, and S. S. Sastry,\n                      Generalized Principal Component Analysis\n                      , Interdiscip. Appl. Math. 40, Springer-Verlag, New York, 2016.","DOI":"10.1007\/978-0-387-87811-9"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(92)90407-2"},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2016.2595761"},{"key":"atypb41","first-page":"515","author":"Zare A.","year":"2015","journal-title":"IL, IEEE"},{"key":"atypb42","doi-asserted-by":"publisher","DOI":"10.1017\/jfm.2016.682"}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/17M1115770","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:52:17Z","timestamp":1787338337000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/17M1115770"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":42,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/17M1115770"],"URL":"https:\/\/doi.org\/10.1137\/17m1115770","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}