Lower bounds for the singular values of submatrices of othogonal matrices

Question

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

Answer 1

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).

Answer 2

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.