3
$\begingroup$

Assume, we have an $m\times n$ block matrix $M=\left[\begin{array}{c c}A&C\\B&D \end{array}\right]$, where

  1. $A$ is an $m_1 \times n_1$ matrix of rank $k_A$.
  2. $B$ is an $m_2 \times n_1$ matrix of rank $k_B$.
  3. $C$ is an $m_1 \times n_2$ matrix of rank $k_C$.
  4. $D$ is an $m_2 \times n_2$ matrix of rank $k_D$.

Obviously, $m_1+m_2=m$ and $n_1+n_2=n$.

In the paper by Carl D. Meyer "Generalized inverses and ranks of block matrices", SIAM J. Appl. Math, vol. 25, no. 4, pp. 597-602, Dec. 1973, I found a way to bound the rank of a block matrix $M$ by the rank of its subblocks, as follows (Corollary 4.1):

$$ \begin{equation} \newcommand{\rank}[1]{\text{rank}(#1)} \rank{M}\leq\rank{A}+\rank{B}+\rank{C}+\rank{Z}, \tag{1}\label{1} \end{equation}$$

where $Z=D-BA^-C$, thus leading to

$$ \begin{equation} \rank{M}\leq k_A+k_B+k_C+\underbrace{\big(k_D+\min(k_A,k_B,k_C)\big)}_{\rank{Z}}, \tag{2}\label{2} \end{equation}$$ as $\rank{Z}\leq \rank{D}+\rank{BA^-C}=k_D+\min(k_A,k_B,k_C)$ by the properties of matrix ranks: rank of a sum and rank of a product. So, we can convert an original result $\eqref{1}$ to $$ \begin{equation} \rank{M}\leq k_A+k_B+k_C+k_D+\min(k_A,k_B,k_C)\leq 5\underbrace{\max{(k_A,k_B,k_C,k_D)}}_{k_\max}. \tag{3}\label{3} \end{equation}$$

I have the following questions:

  1. Is anybody aware of any way to come up with a tighter (than $\eqref{1}$ or $\eqref{3}$) bound to a rank of a $2\times 2$ block matrix in terms of the ranks matrices of its subblocks? The reason is that in my numerical experiments (matrices arise from boundary value problem) I cannot come up even close to this bound (usually staying safely within $2k_\max$) - which proves nothing, but certainly makes me think.
  2. The original paper talks about exact ranks. Would this or any other bound change significantly if we start talking about the numerical rank $\tilde{k}_M(\epsilon)$ in terms of numerical ranks of its subblocks $\tilde{k}_{A,B,C,D}(\epsilon)$? Here $\epsilon$ is the relative tolerance for a truncated SVD. In other words, if $\tilde{k}_{M}(\epsilon)=5$, then $\sigma_6/\sigma_1<\epsilon$. ($\sigma_{1},\ldots,\sigma_{\min(m,n)}$ being the singular values of $M$)
  3. Is there an efficient way to construct a truncated SVD of $M$ from already computed $\epsilon$-truncated SVD's of subblocks $A,B,C,D$? and how to estimate the error in the resultant truncated SVD of the original matrix $M$?
$\endgroup$
  • $\begingroup$ It is important that the A and D blocks be rectangular, as opposed to square? Is it too much to assume that A might be square invertible? $\endgroup$ – Richard Zhang Apr 6 '17 at 17:57
  • $\begingroup$ If $A$ is invertible, it means it is full rank, that is certainly too much. Mostly, I am interested in the situations when all $A,B,C,D$ are low-rank ($k_A \ll \min{(m_1,n_1)}$). For simplicity, we can assume that all the four blocks are square of size $\frac{m}{2}\times\frac{m}{2}$, but I don't think it will make any big difference for this problem. $\endgroup$ – Anton Menshov Apr 6 '17 at 18:29
4
$\begingroup$

Let us begin with the exact singular value decompositions $A=U_{A}S_{A}V_{A}^{T}$, $B=U_{B}S_{B}V_{B}^{T}$, $C=U_{C}S_{C}V_{C}^{T}$, $D=U_{D}S_{D}V_{D}^{T}$. Then $$ M=\underbrace{\begin{bmatrix}U_{A} & 0 & U_{C} & 0\\ 0 & U_{B} & 0 & U_{D} \end{bmatrix}}_{X}\underbrace{\begin{bmatrix}S_{A} & 0 & 0 & 0\\ 0 & S_{B} & 0 & 0\\ 0 & 0 & S_{C} & 0\\ 0 & 0 & 0 & S_{D} \end{bmatrix}}_{S}\underbrace{\begin{bmatrix}V_{A}^{T} & 0\\ V_{B}^{T} & 0\\ 0 & V_{C}^{T}\\ 0 & V_{D}^{T} \end{bmatrix}}_{Y^{T}}\tag{*} $$ is a low-rank decomposition of $M$. This immediately proves $$ \mathrm{rank}(M)\le k_{1}+k_{2}+k_{3}+k_{4}.\tag{**} $$ Note that the bound is not always tight, because $X$, $Y$ are not completely orthogonal. What we can do is compute the QR factors $$ X=Q_{X}R_{X},\qquad Y=Q_{Y}R_{Y}, $$ form the inner matrix $W=R_{X}SR_{Y}^{T}$, and compute its SVD $W=U_{W}\Sigma V_{W}^{T}$. Then $$ M=Q_{X}WQ_{Y}^{T}=\underbrace{Q_{X}U_{W}}_{U}\Sigma\underbrace{V_{W}^{T}Q_{Y}^{T}}_{V^{T}}=U\Sigma V^{T} $$ is the exact singular value decomposition for $M$, and $\mathrm{rank}(M)=\mathrm{rank}(\Sigma)$.

For your questions:

  1. For general rectangular matrices, (**) is the tightest bound we can form without needing to perform linear algebra.

  2. There are many different definitions of numerical ranks. Assuming that you are talking about the truncated SVD rank, i.e. the rank needed for an $\epsilon$ approximation, then the same bound holds due to the result below.

  3. Now suppose that each SVD of $A$, $B$, $C$, $D$ has been truncated to achieve a Frobenius norm bound of $\epsilon$ (that is much greater than machine precision). Then the decomposition (*) has a Frobenius norm bound of $2\epsilon$. If we perform the next two steps to machine precision (which is easy, because the ranks are small), then our resulting SVD for $M$ is also accurate to a Frobenius norm of $2\epsilon$.

$\endgroup$

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.