13
$\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$

2 Answers 2

15
$\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$
1
  • $\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
    Commented Dec 3, 2015 at 13:39
7
$\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
  • 1
    $\begingroup$ Thank you so much for the references, very interesting (+1). $\endgroup$
    – epsilone
    Commented Dec 3, 2015 at 16:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .