Page 66 in this slideset discusses and presents an example for the following idea: given the idea that a (Laplacian, hence square) matrix can be exactly decomposed as

$$ A = U^\top U $$

(which could be obtained by Gaussian elimination), define the approximated decomposition problem

$$ A \approx V^\top V$$

where $V$ is lower rank (notionally even a column vector). The slides give a numerical example rather than the algorithm itself, but there are steps I can't follow (it starts with "Find the rank-1 matrix that agrees on" (in the sense of producing the approximated $V_1^\top V_1$ matrix reproducing) "the first row and column" -- how?).

I guess my question is more like "does this have a name? Is it implemented in linear algebra packages?" than "how exactly is this computed" (because my naive implementation of a detailed explanation would probably suck). Barring that, some light on how "find the low-rank matrix that agrees work" would be immensely appreciated.

  • 1
    $\begingroup$ You should consider asking this here: scicomp.stackexchange.com. $\endgroup$ Aug 3, 2018 at 15:14
  • 1
    $\begingroup$ The algorithm illustrated by the example on slides 67-74 is simply the Cholesky factorization of $A$ (or $L_G$ in notation of slide 66). It looks to me that the further slides discuss some variant of incomplete Cholesky factorization for graph Laplacians to reduce the number of nonzeros in the factors. Note that this is not a low rank approximation though as the factors have full rank. $\endgroup$ Aug 3, 2018 at 15:35


You must log in to answer this question.

Browse other questions tagged .