2
$\begingroup$

Given a block diagonal matrix, is it possible to read out the SVD of its constituent blocks using the SVD of the block diagonal?

When I say block diagonal, it might not necessarily mean that the blocks are square matrices. I am interested in the more general, rectangular case. So a block diagonal in this question's context is a matrix $M$ as follows:

$$ M=\begin{bmatrix} A&0\\ 0&B \end{bmatrix}\quad\textrm{where $A$ and $B$ are rectangular matrices} $$

Given $M = \textrm{block_diag}\left(A,B\right)$ and $M = U_MD_MV_M$ be an SVD of $M$. I can see that the singular values of $A$ and $B$ will be contained in $D_M$. But they might not be in an order which makes it easy to tell which entry of $D_M$ is a singular value for which of $A$ or $B$.

I tried a bunch of simulations using numpy.linalg.svd and the ordering seems pretty random. This is also probably because numpy.linalg.svd outputs the diagonal $D_M$ such that its values are in a non increasing order.

How can I get $U_A, U_B, D_A, D_B, V_A, V_B$ using $U, D, V$ ?

I found a relevant question here but it just gives one particular way of finding SVD of a bock diagonal matrix and doesn't say anything about going from SVD of block-diag to SVD of constituent elements.

$\endgroup$

1 Answer 1

2
$\begingroup$

Consider the block diagonal matrix $M=\begin{bmatrix} 1&1&2&0&0\\ 2&1&3&0&0\\ 0&0&0&1&2\\ 0&0&0&2&1 \end{bmatrix}$

Calculations in Python show that for M, the SVD is as follows: $U=\begin{bmatrix} -0.54&0&0&0.83\\ -0.83&0&0&-0.54\\ 0&0.7&-0.7&0\\ 0&0.7&0.7&0 \end{bmatrix}$

and the vector of singular values is $\Sigma=(4.45, 3, 1, 0.38)$ (Note the non-increasing order) and $V^T=\begin{bmatrix} -0.45&-0.3&-0.09&0&0\\ 0&0&0&0.7&0.7\\ 0&0&0&0.7&-0.7\\ -0.64&0.75&0.10&0&0\\ -0.57&0.57&-0.57&0&0 \end{bmatrix}$

What transformations will make U and $V^T$ block diagonal?

If we swap the 2nd and 4th columns of U, then U will become block diagonal. Suppose this transformation is brought about by right multiplying U with a permutation matrix $P_1$.

Similarly $V^T$ can be made block diagonal by 1) swapping the 2nd and 4th rows and 2) swapping the 3rd and 5th rows. Suppose this transformation is brought about by left multiplying $V^T$ with a permutation matrix $P_2$.

Then the original matrix M can be written as $M = {U}{P_1}{P_1^{-1}}{\Sigma}{P_2^{-1}}{P_2}{V^T}$. Since we have already brought U$P_1$ and $P_2V^T$ into block diagonal forms, it follows that if we are given only the SVD of M and the blocks of M, then the matrix $P_1^{-1}{\Sigma}P_2^{-1}$ will have to be a diagonal matrix of singular values in which the singular values of blocks A and B will be in the right order.

The next question is how do we obtain the permutation matrices $P_1$ and $P_2$? Suffices to show how to shuffle the rows of an already shuffled block diagonal matrix to bring it back into its block diagonal form.

If Q is a row-shuffled block diagonal matrix, how to find a permutation matrix P such that PQ is in block diagonal form? Let n = #rows of Q. Consider the following two non-decreasing subsets Z and NZ of the set {1,2,...,n}:

Z = $(z_1,z_2,...,z_{n1})$ and NZ = $(nz_1,nz_2,...,nz_{n2})$ where $n_1+n_2=n$ and where

$z_i$ = row index when for the i-th time a row of Q has it's first column entry as = 0

$nz_i$ = row index when for the i-th time a row of Q has it's first column entry as != 0

(In above we are scanning rows of Q from the top)

Also $z_1<z_2<...<z_{n1}$ and $nz_1<nz_2<...<nz_{n2}$. Now we construct our permutation matrix P filling row-by-row from the topmost row as follows:

For i = 1,2,...,$n_2$, do the following:

in the i-th row of P, put 0 in all columns except the column $nz_i$ where we put a 1 instead.

Next for i = 1,2,...,$n_1$, do the following:

in the ($n_2$+i)-th row of P, put 0 in all columns except the column $z_i$ where we put a 1 instead. For example, if we apply this algorithm to the matrix $V^T$ we get $P_2=\begin{bmatrix} 1&0&0&0&0\\ 0&0&0&1&0\\ 0&0&0&0&1\\ 0&1&0&0&0\\ 0&0&1&0&0 \end{bmatrix}$

However this algorithm is far from perfect. For example, it assumes $U^T$ or $V^T$ has no 0 in its first column. If they do have a 0 in its first column, then the algorithm will get confused and might possibly give a wrong answer.

One way in which we could possibly remedy this situation is by making use of the Scale-Invariance property of the SVD. Due to this Scale-Invariance property, the singular matrix (which contains the singular values) will not change if we pre-multiply M by a unitary matrix U' and post-multiply by a unitary matrix V'. The new SVD decomposition of U'MV' should be ${U'U}{\Sigma}{VV'}$. That is, only the left and right singular vectors will change but the $\Sigma$ matrix remains the same. So we can choose U' and V' such that ${(U'U)^T}$ has only non-zero entries in its first column for all rows corresponding to block A and the zeros in the first column for all rows corresponding to block B remain as they are, that is they remain 0. Likewise for ${(VV')^T}$. This could possibly be a simpler line of attack to achieving our objective.

We can use the following lemma to build our algorithm:

Lemma: A block diagonal matrix with 2 blocks is unitary if and only if each of its 2 blocks are unitary.

If we make use of this lemma, then we can search for the new unitary matrices U' and V' in block diagonal form.

So now the algorithm goes like this (note that each time an SVD is performed inside the loop, I call the generated matrices U and V only):

While (|NZ| for $U^T$ != number of rows of block A) OR (|NZ| for $V^T$ != number of columns of block B):

Step 1: Generate random unitary matrices ${U_A}'$ with number of columns = number of rows of A

Step 2: Generate random unitary matrices ${U_B}'$ with number of columns = number of rows of B

Step 3: Construct block diagonal matrix U' with blocks ${U_A}'$ and ${U_B}'$

Steps 4,5,6: Do similar steps to construct block diagonal matrix V' with blocks ${V_A}'$ and ${V_B}'$

Step 7: Construct the new matrix M' = U'MV'

Step 8: Perform SVD on M'. This will generate U and V.

Step 9: Generate ordered sets Z and NZ for both U and V

When the loop terminates, we will have both $U^T$ and $V^T$ in block diagonal form with the correct sizes for both |Z| and |NZ|

Then and only then we will be able to create P1 and P2. And then the algorithm will come to an end.

The code for the preliminary computations (not the entire algorithm) done using Python can be found in this link:

https://github.com/nravindranath10/Singular-Value-Decomposition-of-Block-Diagonal-Matrices/blob/main/identifying_singular_values_belonging_to_blocks_from_SVD_on_block_diagonal_matrix_new.py

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .