Explicit Bounds for Restricted Invertibility with Prescribed Group Cardinalities

Abstract

We prove an explicit lower spectral bound for independent random vectors with prescribed group multiplicities. Let $v_{ij}\in {\mathbb{C}}^d$, $1\le i\le l$, $1\le j\le k_i$, be independent random vectors with finite support and $\mathbb{E}{v}_{ij}{v}_{ij}^{\ast }=A_i$, where ${\sum }_{i=1}^l{A}_i=I_d$ and $\mathrm{Tr}(A_i)\ge \epsilon$. Set $k={\max }_i{k}_i$, $n={\max }_i\mathrm{rank}(A_i)$, and $K={\sum }_{i=1}^l{k}_i$. If $n>(6+4\sqrt{2})k$ and $2\sqrt{nk}-k<\epsilon \le n/2$, then, with positive probability, \[ λ_K\left(\sum_{i=1}^l\sum_{j=1}^{k_i}v_{ij}v_{ij}^*\right) \ge n-(\sqrt{k}+\sqrt{n-ε})^2. \] As a consequence, we obtain a restricted invertibility result selecting exactly $k_i$ vectors from the $i$th group of a Parseval frame. The proof combines interlacing families, a reciprocal transformation of mixed characteristic polynomials, and a multivariate barrier estimate that accommodates repeated differentiation in the same variable.