4
$\begingroup$

I have a problem where I need to compute many times the SVD of a "quasi-diagonal" matrix.

What I call a quasi-diagonal matrix is a diagonal matrix, except its last column. For example, an (m+1)-quasi-diagonal matrix: \begin{bmatrix} d_1 & 0 & \dots & 0 & x_1 \\ 0 & d_2 & \ddots & \vdots & \vdots \\ \vdots & \ddots & \ddots & 0 & \vdots \\ \vdots & & \ddots & d_m & x_m \\ 0 & \ldots & \ldots & 0 & p \end{bmatrix} In my case, $d_1,\dots,~d_m,~p > 0$ and $d_1,\dots,~d_m$ are the same for all computations (only $x_1,\dots,~x_m$ and $p$ change).

$m$ is not very large (say $50$ max), but I need to do this many times (~500,000). So, I wonder if there is a clever way to get the SVD of this type of matrix.

Improve this question
$\endgroup$
5
  • $\begingroup$ May be more appropriate at scicomp.stackexchange.com . Is there any relation (commonality) between the 500,000 instances? $\endgroup$
    – Mark L. Stone
    Commented Jan 28, 2017 at 17:36
  • $\begingroup$ The commonality is that $d_1,\dots,~d_m$ are the same across all instances. $\endgroup$
    – F. Privé
    Commented Jan 28, 2017 at 18:47
  • 1
    $\begingroup$ This may not exactly be your situation, but maybe it will get you started down the right path. stat.osu.edu/~dmsl/thinSVDtracking.pdf $\endgroup$
    – Mark L. Stone
    Commented Jan 28, 2017 at 19:44
  • 1
    $\begingroup$ This is exactly what gets me here. This is the matrix K of equation (9). The reference paper they give ([5]) is not very clear. $\endgroup$
    – F. Privé
    Commented Jan 28, 2017 at 19:53
  • 1
    $\begingroup$ Try asking the author for help math.berkeley.edu/~mgu .Have you looked at his thesis on which the tech report is based? $\endgroup$
    – Mark L. Stone
    Commented Jan 28, 2017 at 21:31

1 Answer 1

Reset to default
1
$\begingroup$

These matrices may be called "half arrowhead" matrices. Usually, in SVD computations, the relevant matrix is transformed into a bidiagonal form. The bidiagonal SVD problem is solved using standard algorithms such as the QR-algorithm, the divide & conquer, bisection or the qd-algorithm. I assume that the readers are familiar with Givens (plain) rotations. Otherwise consult a book such as "Matrix Computations" by Gene Golub and Charles Van Loan.

So the problem is essentially how to reduce the arrowhead matrix to the bidiagonal form in an efficient and numerically robust manner.

(a) Apply a Givens (plain) rotation from the left to the rows 1 and 2 to kill the element $x_1$. This will modify the element $x_2$ and creates two elements at (1,2) and (2,1) positions.

(b)Now apply a Given rotations from right to the columns 1 and 2 to kill the element (2,1). This will modify the (1,2) element but no new elements are created.

(c) Ignore the first row and the first column. They are already in the bidiagonal form. Kill the modified $x_2$ element as before. Then kill the newly created (2,3) element as before.

(d) Repeat the process and you have a bidiagonal matrix.

Use a standard algorithm to solve the bidiagonal problem.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks for the name. I don't think I understand everything you said. Just one question: can it used the fact that $d_1, \dots, d_m$ are the same across all instances? $\endgroup$
    – F. Privé
    Commented Mar 17, 2017 at 8:48
  • $\begingroup$ Unfortunately, the $d$s change. However, instead of solving a set of "half-arrowhead matrices' you have a set of bidiagonal matrices which are in the basic reduced form. There are very good algorithms to solve bidiagonal matrices. $\endgroup$
    – Vini
    Commented Mar 18, 2017 at 10:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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