9
$\begingroup$

We know that a real, symmetric, positive definite matrix $A$ of size $n\times n$ can be parametrized by a vector $\theta$ of $\frac{n(n+1)}{2}$ parameters thanks to the Cholesky decomposition: $$ A = L L^T, $$ with $L$ a lower triangular matrix and $\theta=\mathrm{vech}(L)$. The decomposition is unique if the diagonal of $L$ is positive. The diagonal of $L$ can be expressed in log-scale so $\theta$ remains unconstrained. Hence, there is always a unique $\theta$ for a given $A$ and any $A$ can be expressed in such a way. This and other unconstrained parametrizations for positive definite matrices are discussed in this nice paper.

My question is about the existence of a similar, simple and unique parametrization when $A$ is positive semidefinite of rank $r$ (PSDr), or the best approach available. Such parametrization would rely on $\frac{(2p+1-r)r}{2}$ parameters and my intention is to use it for optimization over the set of PSDr.

So far my attempt was to work with a naive extension of the positive definite case: $$ A = L_r L_r^T, $$ where $L_r$ is a $n\times r$ lower triangular matrix. It is easy to see that $A$ can be always factorized in such a way:

  • First, by the spectral theorem, $A=V_r\Lambda_r V_r^T$, where $\Lambda_r=\mathrm{diag}(\lambda_1,\ldots,\lambda_r)$ and $V_r=(v_1,\ldots,v_r)$ is the $n\times r$ orthonormal matrix of the positive $r$ eigenvectors. We also have $A = U_r^T U_r$, with $U_r=V_r\Lambda_r^{1/2}V_r^T$ a $n\times n$ matrix of rank $r$. The decomposition is of course unique.
  • Second, by the reduced rank QR decomposition, $$ U_r=Q_rR_r=Q_rL_r^T, $$ with $Q_r$ a $n\times r$ matrix with orthogonal columns and $R_r$ an $r\times n$ upper triangular matrix. Then, $A=L_rL_r^T$. Apparently, the decomposition is unique if $R_r$ is in row Echelon form with positive leading entries in every row (see related question here). Unfortunately, such parametrization is not-so-nice to work with as it does not display the rank deficiency explicitly.

Alternatively, but closely related, I checked the pivoted Cholesky decomposition as seen here (sorry for the .html) or in Theorem 10.9 of Higham (2009), which I quote here for completeness:

Theorem 10.9. Let $A\in\mathbb R^{n\times n}$ be positive semidefinite of rank $r$. (a) There exists at least one upper triangular $R\in\mathbb R^{n\times n}$ with nonnegative diagonal elements such that $A = R^TR$. (b) There is a permutation $\Pi$ such that $\Pi^TA\Pi$ has a unique Cholesky factorization, which takes the form $$ \Pi^TA\Pi=R^TR,\quad R=\left(\begin{matrix} R_{11} & R_{12} \\ 0 & 0\end{matrix}\right), $$ where $R_{11}$ is $r \times r$ upper triangular with positive diagonal elements.

That result seems to provide the answer to my question, but the problem is the appearance of a permutation matrix $\Pi$, which implies hidden degrees of freedom that are not captured by $R$. Or in other words, you will not know which entries have to be null and which not.

Since I want to stick to a simple parametrization and given that the previous ways lead to not-so-simple solutions, I thought just considering $A=L_rL_r^T$ with $L_r$ constrained to have positive diagonal, so ensuring $A_r$ has always rank $r$. Then I have these questions:

  • Question 1: Is any matrix $A$ in PSDr expressable as $L_rL_r^T$? I guess if the answer is positive, then there will not be a unique way of doing it...
  • Question 2: In case the answer to the previous question is negative, is the set generated by the matrices $L_rL_r^T$ dense in PSDr (with respect to some norm, e.g. Frobenius).

Of course, any thoughts regarding the approach to the problem are much appreciated.

$\endgroup$
13
$\begingroup$

To get a parameterization of the kind you want, the space $S_{n,r}$ of positive semidefinite symmetric $n$-by-$n$ matrices of rank $r$ (with ($0<r<n$) would have to be contractible, but it is not. It is homotopy equivalent to the space $\mathrm{Gr}_r(n)$ consisting of $r$-dimensional subspaces of $\mathbb{R}^n$, and this space has nontrivial topology.

For example, in the first nontrivial case $r=1$, this is the space $S_{n,1}$ of rank $1$ symmetric $n$-by-$n$ matrices, and every $A\in S_{n,1}$ can be written in the form $A = vv^T$ where $v$ is a nonzero vector in $\mathbb{R}^n$, unique up to a choice of sign. Thus, $S_{n,1} = \mathbb{RP}^{n-1}\times\mathbb{R}^+$, and the topology of $\mathbb{RP}^{n-1}$ comes into play. It is not a contractible space when $n>1$.

$\endgroup$
  • $\begingroup$ Thanks for your answer @Robert Bryant (+1). Although this is bad news for the parametrization :(. I guess that if it is dense still could be useful in practise, so I will leave the question opened to try to find an answer to this point. $\endgroup$ – epsilone Dec 3 '15 at 13:39
6
$\begingroup$

This paper considers optimization problems on the set of low-rank PSD matrices, and in particular talks about operating in a quotient space to deal with the non-uniqueness.

See also this work that introduces a Cholesky Manifold to parametrize low-rank PSD matrices.

Both [1] and [2] cited above are written to deal with the parameterization, non-uniqueness, etc. problems that you are trying to address.

Finally, if you want to quickly try out a quotient-geometry parameterization, you may have a look at fixed-rank PSD matrices in the manopt solver.

$\endgroup$
  • 1
    $\begingroup$ Thank you so much for the references, very interesting (+1). $\endgroup$ – epsilone Dec 3 '15 at 16:42

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.