<p>This paper delves into the spectral norm aspect of the Generalized Column and Row Subset Selection (GCRSS) problem. Given a target matrix <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$\textbf{A}\in \mathbb {R}^{n\times d}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="bold">A</mi> <mo>∈</mo> <msup> <mrow> <mi mathvariant="double-struck">R</mi> </mrow> <mrow> <mi>n</mi> <mo>×</mo> <mi>d</mi> </mrow> </msup> </mrow> </math></EquationSource> </InlineEquation>, the objective of GCRSS is to select a column submatrix <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$\textbf{B}_{:,S}\in \mathbb {R}^{n\times k}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi mathvariant="bold">B</mi> <mrow> <mo>:</mo> <mo>,</mo> <mi>S</mi> </mrow> </msub> <mo>∈</mo> <msup> <mrow> <mi mathvariant="double-struck">R</mi> </mrow> <mrow> <mi>n</mi> <mo>×</mo> <mi>k</mi> </mrow> </msup> </mrow> </math></EquationSource> </InlineEquation> from the source matrix <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$\textbf{B}\in \mathbb {R}^{n\times d_B}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="bold">B</mi> <mo>∈</mo> <msup> <mrow> <mi mathvariant="double-struck">R</mi> </mrow> <mrow> <mi>n</mi> <mo>×</mo> <msub> <mi>d</mi> <mi>B</mi> </msub> </mrow> </msup> </mrow> </math></EquationSource> </InlineEquation> and a row submatrix <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$\textbf{C}_{R,:}\in \mathbb {R}^{r\times d}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi mathvariant="bold">C</mi> <mrow> <mi>R</mi> <mo>,</mo> <mo>:</mo> </mrow> </msub> <mo>∈</mo> <msup> <mrow> <mi mathvariant="double-struck">R</mi> </mrow> <mrow> <mi>r</mi> <mo>×</mo> <mi>d</mi> </mrow> </msup> </mrow> </math></EquationSource> </InlineEquation> from the source matrix <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$\textbf{C}\in \mathbb {R}^{n_C\times d}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="bold">C</mi> <mo>∈</mo> <msup> <mrow> <mi mathvariant="double-struck">R</mi> </mrow> <mrow> <msub> <mi>n</mi> <mi>C</mi> </msub> <mo>×</mo> <mi>d</mi> </mrow> </msup> </mrow> </math></EquationSource> </InlineEquation>, such that the residual matrix <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$(\textbf{I}_n-\textbf{B}_{:,S}\textbf{B}_{:,S}^{\dagger })\textbf{A}(\textbf{I}_d-\textbf{C}_{R,:}^{\dagger } \textbf{C}_{R,:})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mrow> <mo stretchy="false">(</mo> <msub> <mi mathvariant="bold">I</mi> <mi>n</mi> </msub> <mo>-</mo> <msub> <mi mathvariant="bold">B</mi> <mrow> <mo>:</mo> <mo>,</mo> <mi>S</mi> </mrow> </msub> <msubsup> <mi mathvariant="bold">B</mi> <mrow> <mo>:</mo> <mo>,</mo> <mi>S</mi> </mrow> <mo>†</mo> </msubsup> <mo stretchy="false">)</mo> </mrow> <mi mathvariant="bold">A</mi> <mrow> <mo stretchy="false">(</mo> <msub> <mi mathvariant="bold">I</mi> <mi>d</mi> </msub> <mo>-</mo> <msubsup> <mi mathvariant="bold">C</mi> <mrow> <mi>R</mi> <mo>,</mo> <mo>:</mo> </mrow> <mo>†</mo> </msubsup> <msub> <mi mathvariant="bold">C</mi> <mrow> <mi>R</mi> <mo>,</mo> <mo>:</mo> </mrow> </msub> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> has a small spectral norm. By employing the method of interlacing polynomials, we show that the smallest possible spectral norm of a residual matrix can be bounded by the largest root of a related expected characteristic polynomial. A deterministic polynomial time algorithm is provided for the spectral norm case of the GCRSS problem. We next apply our results to two specific GCRSS scenarios, one where <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$r=0$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>r</mi> <mo>=</mo> <mn>0</mn> </mrow> </math></EquationSource> </InlineEquation>, simplifying the problem to the Generalized Column Subset Selection (GCSS) problem, and the other where <InlineEquation ID="IEq8"> <EquationSource Format="TEX">$\textbf{B}=\textbf{C}=\textbf{I}_d$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="bold">B</mi> <mo>=</mo> <mi mathvariant="bold">C</mi> <mo>=</mo> <msub> <mi mathvariant="bold">I</mi> <mi>d</mi> </msub> </mrow> </math></EquationSource> </InlineEquation>, reducing the problem to the submatrix selection problem. In the GCSS scenario, we connect the expected characteristic polynomials to the convolution of multi-affine polynomials, leading to the derivation of the first provable reconstruction bound on the spectral norm of a residual matrix. In the submatrix selection scenario, we show that for any sufficiently small <InlineEquation ID="IEq9"> <EquationSource Format="TEX">$\varepsilon >0$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>ε</mi> <mo>></mo> <mn>0</mn> </mrow> </math></EquationSource> </InlineEquation> and any square matrix <InlineEquation ID="IEq10"> <EquationSource Format="TEX">$\textbf{A}\in \mathbb {R}^{d\times d}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="bold">A</mi> <mo>∈</mo> <msup> <mrow> <mi mathvariant="double-struck">R</mi> </mrow> <mrow> <mi>d</mi> <mo>×</mo> <mi>d</mi> </mrow> </msup> </mrow> </math></EquationSource> </InlineEquation>, there exist two subsets <InlineEquation ID="IEq11"> <EquationSource Format="TEX">$S\subset [d]$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>S</mi> <mo>⊂</mo> <mo stretchy="false">[</mo> <mi>d</mi> <mo stretchy="false">]</mo> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq12"> <EquationSource Format="TEX">$R\subset [d]$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>R</mi> <mo>⊂</mo> <mo stretchy="false">[</mo> <mi>d</mi> <mo stretchy="false">]</mo> </mrow> </math></EquationSource> </InlineEquation> of sizes <InlineEquation ID="IEq13"> <EquationSource Format="TEX">$O(d\cdot \varepsilon ^2)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <mi>d</mi> <mo>·</mo> <msup> <mi>ε</mi> <mn>2</mn> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> such that <InlineEquation ID="IEq14"> <EquationSource Format="TEX">$\Vert \textbf{A}_{S,R}\Vert _2\le \varepsilon \cdot \Vert \textbf{A}\Vert _2$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mrow> <mo stretchy="false">‖</mo> </mrow> <msub> <mi mathvariant="bold">A</mi> <mrow> <mi>S</mi> <mo>,</mo> <mi>R</mi> </mrow> </msub> <msub> <mrow> <mo stretchy="false">‖</mo> </mrow> <mn>2</mn> </msub> <mo>≤</mo> <mi>ε</mi> <mo>·</mo> <msub> <mrow> <mo stretchy="false">‖</mo> <mi mathvariant="bold">A</mi> <mo stretchy="false">‖</mo> </mrow> <mn>2</mn> </msub> </mrow> </math></EquationSource> </InlineEquation>. Unlike previous studies that have produced comparable results for very special cases where the matrix is either a zero-diagonal or a positive semidefinite matrix, our results apply universally to any square matrix <InlineEquation ID="IEq15"> <EquationSource Format="TEX">$\textbf{A}$</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="bold">A</mi> </math></EquationSource> </InlineEquation>.</p>

Interlacing Polynomial Method for Matrix Approximation via Generalized Column and Row Selection

期刊论文
发表日期：

2025年7月14日

查看全文

Jian-Feng Cai,
Zhiqiang Xu,
Zili Xu

摘要

This paper delves into the spectral norm aspect of the Generalized Column and Row Subset Selection (GCRSS) problem. Given a target matrix $\textbf{A}\in \mathbb {R}^{n\times d}$ $A \in R^{n \times d}$ , the objective of GCRSS is to select a column submatrix $\textbf{B}_{:,S}\in \mathbb {R}^{n\times k}$ $B_{:, S} \in R^{n \times k}$ from the source matrix $\textbf{B}\in \mathbb {R}^{n\times d_B}$ $B \in R^{n \times d_{B}}$ and a row submatrix $\textbf{C}_{R,:}\in \mathbb {R}^{r\times d}$ $C_{R, :} \in R^{r \times d}$ from the source matrix $\textbf{C}\in \mathbb {R}^{n_C\times d}$ $C \in R^{n_{C} \times d}$ , such that the residual matrix $(\textbf{I}_n-\textbf{B}_{:,S}\textbf{B}_{:,S}^{\dagger })\textbf{A}(\textbf{I}_d-\textbf{C}_{R,:}^{\dagger } \textbf{C}_{R,:})$ $(I_{n} - B_{:, S} B_{:, S}^{†}) A (I_{d} - C_{R, :}^{†} C_{R, :})$ has a small spectral norm. By employing the method of interlacing polynomials, we show that the smallest possible spectral norm of a residual matrix can be bounded by the largest root of a related expected characteristic polynomial. A deterministic polynomial time algorithm is provided for the spectral norm case of the GCRSS problem. We next apply our results to two specific GCRSS scenarios, one where $r=0$ $r = 0$ , simplifying the problem to the Generalized Column Subset Selection (GCSS) problem, and the other where $\textbf{B}=\textbf{C}=\textbf{I}_d$ $B = C = I_{d}$ , reducing the problem to the submatrix selection problem. In the GCSS scenario, we connect the expected characteristic polynomials to the convolution of multi-affine polynomials, leading to the derivation of the first provable reconstruction bound on the spectral norm of a residual matrix. In the submatrix selection scenario, we show that for any sufficiently small $\varepsilon >0$ $ε > 0$ and any square matrix $\textbf{A}\in \mathbb {R}^{d\times d}$ $A \in R^{d \times d}$ , there exist two subsets $S\subset [d]$ $S \subset [d]$ and $R\subset [d]$ $R \subset [d]$ of sizes $O(d\cdot \varepsilon ^2)$ $O (d \cdot ε^{2})$ such that $\Vert \textbf{A}_{S,R}\Vert _2\le \varepsilon \cdot \Vert \textbf{A}\Vert _2$ $‖ A_{S, R} ‖_{2} \leq ε \cdot {‖ A ‖}_{2}$ . Unlike previous studies that have produced comparable results for very special cases where the matrix is either a zero-diagonal or a positive semidefinite matrix, our results apply universally to any square matrix $\textbf{A}$ $A$ .