Skip to main content
SpringerLink
Log in

A variational approach of the rank function

  • Invited Paper
  • Published:
TOP Aims and scope Submit manuscript

Abstract

In the same spirit as the one of the paper (Hiriart-Urruty and Malick in J. Optim. Theory Appl. 153(3):551–577, 2012) on positive semidefinite matrices, we survey several useful properties of the rank function (of a matrix) and add some new ones. Since the so-called rank minimization problems are the subject of intense studies, we adopt the viewpoint of variational analysis, that is the one considering all the properties useful for optimizing, approximating or regularizing the rank function.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4

Similar content being viewed by others

Notes

  1. D “pseudo-diagonal” means that d ij =0 for \(i\not=j\). One also uses the notation \(\operatorname{diag}_{m,n}[\sigma_{1},\dots,\sigma_{p}]\) for D.

  2. The notation for the SVD is a bit nonstandard. Usually, a singular value decomposition takes the form UΣV T (i.e., V T instead of V). But there is no difference from the mathematical point of view.

  3. A nonempty closed set S is an Euclidean space E is called prox-regular at a point \(\overline{x}\in S\) if the projection set P S (x) of x on S is single-valued around \(\overline{x}\).

  4. Such a phenomenon happens because the objective function is not continuous. Indeed, if \(\mathcal {C}\) is a connected set, if \(f:\mathcal{C} \longrightarrow\mathbb{R}\) is a continuous function, and if every point in \(\mathcal{C}\) is a local minimizer or a local maximizer of f, then f is necessarily constant on \(\mathcal{C}\) (see Behrends et al. 2007).

  5. The convex hull or convex envelope of a function f is the largest possible convex function below f. Its epigraph (i.e., what is above the graph) is exactly the convex hull of the epigraph of f (see Hiriart-Urruty and Lemaréchal 1993).

  6. J.-J. Moreau presented this approximation process as an example of inf-convolution or epigraphic addition of two functions; it was in 1962, exactly 50 years ago. This date marks the birth of modern convex analysis and optimization.

  7. D. Drusvyatskiy, personal communication (August 2012).

References

  • Absil P-A, Malick J (2012) Projection-like retractions on matrix manifolds. SIAM J Optim 22(1):135–158

    Article  Google Scholar 

  • Attouch H, Bolte J, Svaiter BF (2011) Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss–Seidel method. Math Program. doi:10.1007/s10107-011-0484-9

    Google Scholar 

  • Barioli F (2002) Completely positive matrices of small and large acute sets of vectors. Talk at the 10th ILAS Conference in Auburn

  • Barioli F, Berman A (2003) The maximal cp-rank of rank k completely positive matrices. Linear Algebra Appl 363:17–33

    Article  Google Scholar 

  • Behrends E, Geschke S, Natkaniec T (2007) Functions for which all points are local extrema. Real Anal Exch 33(2):467–470

    Google Scholar 

  • Berman A, Shaked-Monderer N (1998) Remarks on completely positive matrices. Linear Multilinear Algebra 44(2):149–163

    Article  Google Scholar 

  • Berman A, Shaked-Monderer N (2003) Completely positive matrices. World Scientific, Singapore

    Book  Google Scholar 

  • Bernstein DS (2005) Matrix mathematics: theory, facts, and formulas. Princeton University Press, Princeton

    Google Scholar 

  • Bomze I (2012) Copositive optimization—recent developments and applications. Eur J Oper Res 216:509–520

    Article  Google Scholar 

  • Bruckstein AM, Donoho DL, Elad M (2009) From sparse solutions of systems of equations to sparse modeling of signals and images. SIAM Rev 51(1):34–81

    Article  Google Scholar 

  • Clarke FH (1983) Optimisation and nonsmooth analysis. Wiley, New York

    Google Scholar 

  • Clarke FH, Ledyaev YS, Stern RT, Wolenski PR (1998) Nonsmooth analysis and control theory. Springer, Berlin

    Google Scholar 

  • Donoho D, Elad M (2003) Optimally sparse representation in general (nonorthogonal) dictionaries via 1 minimization. Publ Natl Acad Sci 100(5):2197–2202

    Article  Google Scholar 

  • Drew JH, Johnson CR, Loewy R (1994) Completely positive matrices associated with M-matrices. Linear Multilinear Algebra 37:303–310

    Article  Google Scholar 

  • Drusvyatskiy D, Lewis AS (2013) Semi-algebraic functions have small subdifferentials. Math Program Ser B. doi:10.1007/s10107-012-0624-x. Special issue in honor of C. Lemaréchal

    Google Scholar 

  • Drusvyatskiy D, Ioffe AD, Lewis AS (2012) The dimension of semialgebraic subdifferential graphs. Nonlinear Anal 75:1231–1245

    Article  Google Scholar 

  • Dür M (2010) Copositive programming—a survey. In: Recent advances in optimization and its applications in engineering, pp 3–20. Part 1. doi:10.1007/978-3-642-12598-0-1

    Chapter  Google Scholar 

  • Eckart C, Young G (1936) The approximation of one matrix by another of lower rank. Psychometrika 1:211–218

    Article  Google Scholar 

  • Elad M (2010) Sparse and redundant representations: from theory to applications in signal and image processing. Springer, Berlin

    Book  Google Scholar 

  • Fazel M (2002) Matrix rank minimization with applications. Ph.D. thesis, Stanford University

  • Flores S (2011) Problèmes d’optimisation globale en statistique robuste. Ph.D. thesis, Paul Sabatier University, Toulouse

  • Hanna J, Laffey TJ (1983) Nonnegative factorization of completely positive matrices. Linear Algebra Appl 55:1–9

    Article  Google Scholar 

  • Higham N (1989) Matrix nearness problems and applications. In: Gover MJC, Barnett S (eds) Applications of matrix theory. Oxford University Press, London, pp 1–27

    Google Scholar 

  • Hiriart-Urruty J-B (2009) Deux questions de rang. Working Note, Paul Sabatier University

  • Hiriart-Urruty J-B (2012) When only global optimization matters. J Glob Optim. doi:10.1007/s10898-011-9826-7

    Google Scholar 

  • Hiriart-Urruty J-B, Le HY (2011) Convexifying the set of matrices of bounded rank: applications to the quasiconvexification and convexification of the rank function. Optim Lett. doi:10.1007/s11590-011-0304-4

    Google Scholar 

  • Hiriart-Urruty J-B, Le HY (2012) From Eckart & Young approximation to Moreau envelopes and vice versa. Preprint (submitted)

  • Hiriart-Urruty J-B, Lemaréchal C (1993) Convex analysis and minimization algorithms. Springer, Berlin

    Google Scholar 

  • Hiriart-Urruty J-B, Malick J (2012) A fresh variational analysis look at the world of the positive semidefinite matrices. J Optim Theory Appl 153(3):551–577

    Article  Google Scholar 

  • Hiriart-Urruty J-B, Seeger A (2010) A variational approach to copositive matrices. SIAM Rev 54(4):593–629

    Article  Google Scholar 

  • Horn RA, Johnson CR (1975) Matrix analysis. Cambridge University Press, Cambridge

    Google Scholar 

  • Jourani A, Thibault L, Zagrodny D (2012) Differential properties of Moreau envelope. Preprint

  • Kruskal JB (1977) Three-way arrays: rank and uniqueness of trilinear decomposition, with application to arithmetic complexity and statistics. Linear Algebra Appl 18(2):95–138

    Article  Google Scholar 

  • Le HY (2012a) Convexifying the counting function on \(\mathbb{R}^{p}\) for convexifying the rank function on \(\mathcal{M}_{m,n}(\mathbb{R})\). J Convex Anal 19(2)

  • Le HY (2012b) The generalized subdifferentials of the rank function. Optim Lett. doi:10.1007/s11590-012-0456-x

    Google Scholar 

  • Le HY (2013) Ph.D. Thesis. Paul Sabatier University. To be defended in 2013

  • Lewis AS (1995) The convex analysis of unitarily invariant matrix functions. J Convex Anal 2(1):173–183

    Google Scholar 

  • Lewis AS (1996) Convex analysis on the Hermitian matrices. SIAM J Optim 6:164–177

    Article  Google Scholar 

  • Lewis AS, Mallick J (2008) Alternating projections on manifolds. Math Oper Res 33:216–234

    Article  Google Scholar 

  • Lewis AS, Sendov HS (2005a) Nonsmooth analysis of singular values. Part I: theory. Set-Valued Anal 13:213–241

    Article  Google Scholar 

  • Lewis AS, Sendov HS (2005b) Nonsmooth analysis of singular values. Part II: applications. Set-Valued Anal 13:243–264

    Article  Google Scholar 

  • Lim L-H, Common P (2010) Multiarray signal processing: tensor decomposition meets compressed sensing. Preprint

  • Liu Y-J, Sun D, Toh K-C (2012) An implementable proximal point algorithmic framework for nuclear norm minimization. Math Program 133:399–436

    Article  Google Scholar 

  • Loewy R, Tam B-S (2003) CP-rank of completely positive matrices of order 5. Linear Algebra Appl 363:161–176

    Article  Google Scholar 

  • Lokam SV (2001) Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity. J Comput Syst Sci 63:449–473

    Article  Google Scholar 

  • Luke DR (2012) Prox-regularity of rank constraint sets and implications for algorithms. J Math Imaging Vis. doi:10.1007/s10851-012-0406-3

    Google Scholar 

  • Malick J (2007) The spherical constraint in Boolean quadratic programs. J Glob Optim 39:609–622

    Article  Google Scholar 

  • Mirsky L (1960) Symmetric gauge functions and unitary invariant norms. Q J Math 11:50–59

    Article  Google Scholar 

  • Parrilo PA (2009) The convex algebraic geometry of rank minimization. Plenary talk at the International symposium on mathematical programming, Chicago

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

    Article  Google Scholar 

  • Rockafellar RT, Wets RJ-B (1998) Variational analysis. Springer, Berlin

    Book  Google Scholar 

  • Stewart GW (1993) On the early history of the singular value decomposition. SIAM Rev 35(4):551–556

    Article  Google Scholar 

  • Valiant LG (1977) Graph theoretic arguments in low-level complexity. In: Lecture notes in computer science, vol 53. Springer, Berlin, pp 162–176

    Google Scholar 

  • Zhao Y-B (2012) An approximation theory of matrix rank minimization and its application to quadratic equations. Linear Algebra Appl 77–93

Download references

Acknowledgements

We thank the various readers or referees who, after the first circulation of this survey paper (July 2012), provided comments, improvements and additional references.

Last but not least, we would like to thank Professor M. Goberna (University of Alicante) for his instrumental role in the publication of this survey paper.

Author information

Authors and Affiliations

  1. Institute of Mathematics, Paul Sabatier University, Toulouse, France

    Jean-Baptiste Hiriart-Urruty & Hai Yen Le

Authors
  1. Jean-Baptiste Hiriart-Urruty
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Hai Yen Le
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Hai Yen Le.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Hiriart-Urruty, JB., Le, H.Y. A variational approach of the rank function. TOP 21, 207–240 (2013). https://doi.org/10.1007/s11750-013-0283-y

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11750-013-0283-y

Keywords

Mathematics Subject Classification

Search

Navigation