2
$\begingroup$

If $\Sigma$ is a diagonal matrix and $\vec{x}$ a vector, is there a simple formula for the singular values of the matrix $[\Sigma, \vec{x}]$?


A hint: first, write out our matrix $[\Sigma,\vec{x}]$ as

$\left(\begin{array}{cccc} \sigma_1 & & & x_1 \\ & \ddots & & \vdots \\ & & \sigma_n & x_n \end{array}\right)$

Then the rightmost column of the right singular vectors is a basis vector for the nullspace of $[\Sigma,\vec{x}]$ and is proportional to

$\left(\begin{array}{c} -x_1/\sigma_1 \\ \vdots \\ -x_n/\sigma_n \\ 1\end{array}\right)$

Perhaps this can be used as a starting point for a solution.


Edit Apparently a solution to a more general problem can be found in the paper "Updating the Singular Value Decomposition" by J. R. Bunch and C. P. Nielsen. The solution for the eigenvalues involves solving a rational equation and it seems a closed form solution is not practical.

$\endgroup$
  • 1
    $\begingroup$ What does the bracket notation mean? Can you define $[ \Sigma, \vec{x} ]$? $\endgroup$ – Sammy Black Mar 21 '13 at 21:22
  • 1
    $\begingroup$ I presume it means 'stack' $x$ to the right of the diagonal matrix $\Sigma$? $\endgroup$ – copper.hat Mar 21 '13 at 21:22
  • $\begingroup$ I think copper.hat is right. Isn't it clear from concatenated? $\endgroup$ – Git Gud Mar 21 '13 at 21:23
  • $\begingroup$ I thought I knew what "concatenated" and what "stack" mean, yet I still don't understand what does this mean in this context... $\endgroup$ – DonAntonio Mar 21 '13 at 21:28
  • $\begingroup$ I think he means something like: given $A=\begin{pmatrix} y & 0 \\ 0 & z \end{pmatrix}$ and $\vec{x}=[a\space b]^T$, then $$[A,\vec{x}]=\begin{pmatrix} y & 0 & a \\ 0 & z & b\end{pmatrix}$$ $\endgroup$ – Git Gud Mar 21 '13 at 21:33
1
$\begingroup$

If $A$ is your matrix, $A^T A$ is a rank-2 perturbation of a diagonal matrix, so you should be able to apply the Matrix determinant lemma

EDIT: even better, $A A^T = \Sigma^2 + x x^T$ is a rank-1 perturbation of the diagonal matrix $\Sigma^2$. Its characteristic polynomial is then $$ P(\lambda) = \left(1 + \sum_j (\sigma_j^2-\lambda)^{-1} x_j^2\right) \prod_k (\sigma_k^2 - \lambda) = \prod_k (\sigma_k^2 - \lambda) + \sum_j x_j^2 \prod_{k \ne j} (\sigma_k^2 - \lambda)$$ where $\sigma_j$ are the diagonal elements of $\Sigma$. So you need to solve that for $\lambda$ and take square roots to get the singular values.

$\endgroup$
  • $\begingroup$ Interesting...how would I use that to get the singluar values? $\endgroup$ – David Pfau Mar 21 '13 at 21:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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