Matrix Lower-Rank Factorization for L'L = A?

Question

Assume we have Real, Symmetric, and PSD matrix $\textbf{A} \in \mathbb{R}^{n \times n}$, and $\textbf{A}$ has rank $r, \; r < n$.

Then, $\textbf{A}$ will have the factorization of, $\textbf{A} = \textbf{L}^\text{T}\textbf{L}$, with $\textbf{L} \in \mathbb{R}^{r \times n}$.

What is the known efficient algorithm for this?

Thanks for kind advice :)

Answer 1

Just taking 'major non-zero (eigenvalues' corresponding) eigenvectors' with sqrt(major eigenvalues) should work. ( This is for symmetric and PSD matrix ).

Experiment

[ min(resV) ][ 6.579e-14 ]

[ max(resV) ][ 1.084e-12 ]

[ mean(resV)][ 3.247e-13 ]

[ med(resV) ][ 3.013e-13 ]

@ rank(A) = 2, for 200x200 Matrix.

Number of trials 5e+03

Matlab script.

clc, close all;
clear;

tic;

rr  = 2;
n   = rr * 1e2;

m   = 1e5;
v   = 1e3;

nT  = 5e3;

resV = zeros(nT, 1);
for k = 1 : nT

    fprintf('\t[ %05d / %05d ]\n', k, nT);

    S = random('normal', 0, 1, rr, n);
    S = S' * S;

    w           = rank(S);                  % internal rank computation
    n           = size(S, 2);
    [V, D]      = eig(S);
    [~, idx]    = GetLeadingEigen( D );     % largest to the front
    idx         = idx(1:w);
    v           = V(:, idx);
    d           = sqrt(D(idx, idx));
    L           = (v * d)';
    resV(k, 1)  = norm(S - L'*L, 'fro');
end

fprintf('\n\t%s\t@ rank(A) = %d\n\t [ %3.3e ][ %3.3e ][ %3.3e ][ %3.3e ]\t%s %dx%d S.', ...
    ' [ min(resV) ][ max(resV) ][ mean(resV)][ med(resV) ]', ...
    rr, min(resV), max(resV), mean(resV), median(resV)', ...
    'for', n, n);

fprintf('\n\n\n\t\t'); toc;
fprintf('\t\tNumber of trials %3.0e\n\n\n', nT)