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.
Best Answer
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$.