4
$\begingroup$

Let $A$ be an $m \times n$ matrix, $m\geq n$, and let $A=U\Sigma V^T$ be its singular value decomposition.

Let us partition $A$ as $A=(A_1|A_2)$, where $A_1$ is of size $m \times k$, and all columns of $A_2$ are linear combinations of the columns of $A_1$. The columns of $A_1$ are linearly independent, so rank$(A)=k$.

Let us consider permutation matrices $\Pi_{i,k}$ that switch columns $i$ and $k$, where $1 \leq i\leq k$. That is, permutations are restricted to the first $k$ columns. Let us partition $\Pi_{i,k}$ and $V$ as $\Pi_{i,k}=(\Pi_1|\Pi_2)$, $V=(V_1|V_2)$ where $\Pi_1,V_1$ are of size $n\times k-1$.

For each $\Pi_{i,k}$, we consider a submatrix of $V$ defined as $$ V_{i,k}'= \Pi_2^TV_2 $$

If we denote the smallest singular value of some matrix $M$ as $\sigma_{min}(M)$, we consider the permutation $\Pi_{i,k}$ such that $\sigma_{min}(V_{i,k}')$ is maximized.

Can we provide a lower bound for $\sigma_{min}(V_{i,k}')$ ?

The following reference might be helpful. In

Hong, Yoo Pyo, and C-T. Pan. "Rank-revealing 𝑄𝑅 factorizations and the singular value decomposition." Mathematics of Computation 58.197 (1992): 213-232.

a bound is given for general permutations $\Pi$.

The ultimate purpose is to bound the lower-right $n-k+1 \times n-k+1$ block of matrix $R$ in the $QR$ factorization of the permuted matrix $A$.

$\endgroup$
2
$\begingroup$

The following paper might be helpful:

Thompson, R.C. Principal submatrices. IX: Interlacing inequalities for singular values of submatrices. (English) Zbl 0252.15009 Linear Algebra Appl. 5, 1-12 (1972).

$\endgroup$
  • $\begingroup$ I don't think the interlacing inequalities can help me here, as the only bound they imply for the $k+1$-th singular value in this case is 0, but that series of papers can certainly be helpful. $\endgroup$ – cangrejo Mar 24 '17 at 12:26
2
$\begingroup$

I don't think so.

According to

Hong, Yoo Pyo, and C-T. Pan. "Rank-revealing 𝑄𝑅 factorizations and the singular value decomposition." Mathematics of Computation 58.197 (1992): 213-232.

the following holds (theorem 1.5): $$ \|R_{22}\|_2 \leq \frac{1}{\sigma_{\min}(\Pi_2^TV_2)}\sigma_{k}(A) $$ where $A=QR$ is the QR decomposition of $A$.

The quantity $\|R_{22}\|_2$ automatically induces a bound on $\|R_{22}\|_F$, where $R_{22}$ is the $n-k+1\times n-k+1$ block I was referring to. Therefore, a lower bound on $\sigma_{\min}V_{i,k}'$ implies an upper bound on $\|R_{22}\|_F^2=\|A-P_{A_1\Pi_1}(A)\|_F^2$, where $P_{A_1\Pi_1}(A)$ is the projection of $A$ onto the span of the $k-1$ columns of $A_1\Pi_1$.

Let us consider matrices $A \in \mathbb R^{m\times 3}$, whose columns are the vectors $u,v,w$, and $C$, whose columns are $u,v$. Let $\hat w=P_C(w)$

Let us assume $$ v=\left ( \begin{array}{c} u_1+\epsilon \\ \vdots \\ u_m+\epsilon \end{array} \right ) $$ and $\langle u,\hat w \rangle=0$

Now, consider the column matrix $\tilde C$, resulting from removing $u$ from $C$. We have $$ \|P_C(A)\|_F^2-\|P_{\tilde C}(A)\|_F^2 \geq \|P_C(\hat w)\|_F^2-\|P_{\tilde C}(\hat w)\|_F^2 = \|\tilde w\|_2^2 - \|\frac{vv^T}{v^Tv}\tilde w\|_2^2 $$ Now, $$ \frac{vv^T}{v^Tv}\tilde w = \frac{v}{v^Tv}\sum_i(u_i+\epsilon)\tilde w_i=\frac{v}{v^Tv}\sum_i u_i \tilde w_i +\epsilon \tilde w_i = \frac{v}{v^Tv}\epsilon\sum_i \tilde w_i $$ Therefore, $$ \|P_C(A)\|_F^2-\|P_{\tilde C}(A)\|_F^2 \geq \|\tilde w\|_2^2-\epsilon^2 \left \| \frac{v}{v^Tv}\sum_i \tilde w_i \right \|_2^2 $$

In the above framework, this is an instance where $A_1=C,A_2=\tilde w$. By decreasing $\epsilon$, we can obtain a lower bound for $\|R_{22}\|_F^2$ arbitrarily close to $\|A_2\|_F^2$, which implies that we cannot hope for any bound for $\sigma_{\min}(\Pi_2^TV_2)$ better than a trivial one.

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