3
$\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.

$\endgroup$
  • $\begingroup$ May be more appropriate at scicomp.stackexchange.com . Is there any relation (commonality) between the 500,000 instances? $\endgroup$ – Mark L. Stone Jan 28 '17 at 17:36
  • $\begingroup$ The commonality is that $d_1,\dots,~d_m$ are the same across all instances. $\endgroup$ – F. Privé Jan 28 '17 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 Jan 28 '17 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é Jan 28 '17 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 Jan 28 '17 at 21:31
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.

$\endgroup$
  • $\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é Mar 17 '17 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 Mar 18 '17 at 10:07

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.