# Group-theoretic constructions of erasure-robust frames

Sorry it took so long to update this blog. Boris will be the first to tell me that I’m in violation of the law, but I assure you I have been rather busy. I started teaching today, so I used the last couple of months to knock out some research before it was too late!

Last time, I discussed three open problems involving short, fat matrices. Each of these problems concerned the conditioning of submatrices, and in this post, I discuss some new and exciting work along this vein. Specifically, this is about a paper that I just wrote with Matt FickusJohn Jasper and Jesse Peterson, which analyzes a special class of short, fat matrices for which it is relatively tractable to estimate extreme singular values over all submatrices of a certain size.

In this paper, there is no single key idea we exploit, but rather a series of important observations. First, we focus on submatrices of columns which are also short and fat; having these sorts of submatrices be well conditioned is important for numerical erasure robustness. For these submatrices, say $\Phi_\mathcal{K}$ is a submatrix of $\Phi$, the smallest and largest singular values can be visualized in terms of the column vectors that make up the submatrices. Specifically, we get these singular values by minimizing and maximizing $\|\Phi_\mathcal{K}^*x\|$ over all unit vectors $x$, and so we expect these values to be more extreme for subcollections $\mathcal{K}$ of columns which are more bunched up in the sphere.

In this case, we can switch the order of optimization:

$\displaystyle{\max_{|\mathcal{K}|=K}\max_{\|x\|=1}\|\Phi_\mathcal{K}^*x\|=\max_{\|x\|=1}\max_{|\mathcal{K}|=K}\|\Phi_\mathcal{K}^*x\|}$

so that instead of calculating singular values of all $\binom{N}{K}$ submatrices, we find the $K$ columns of $\Phi$ which are closest each unit-norm vector $x$. Of course, there is a continuum of such $x$‘s, i.e., many more than $\binom{N}{K}$. However, we can approximate the extrema of our objective function over the sphere by sampling the sphere at sufficiently many points. Indeed, this application of $\varepsilon$-nets is already old hat in the random matrix community, which uses this sort of discretization of the sphere to perform a union bound. However, they only use the existence of certain sized $\varepsilon$-nets to obtain probability estimates, whereas we explicitly construct $\varepsilon$-nets with certain desirable properties.

Indeed, we don’t want to have to compute our objective function at every point in an $\varepsilon$-net because the smallest known $\varepsilon$-nets of the sphere grow exponentially with the dimension. To decrease the number of operations, we seek a special type of $\varepsilon$-net, namely, one which shares a (large) symmetry group with the columns of $\Phi$. To be explicit, denote $\Phi=\{\varphi_n\}_{n=1}^N$ and take the $\varepsilon$-net $\{U\psi_r\}_{r=1,~U\in G}^R$ to be generated by the symmetry group $G$ of $\Phi$, which is a subgroup of the orthogonal group $O(M)$. By the definition of the symmetry group of $\Phi$, we have that for every $U\in G$, there exists a permutation $\sigma\in S_N$ such that $U\varphi_n=\pm\varphi_{\sigma(n)}$. Using this fact, we have

$\displaystyle{|\langle U\psi_r,\varphi_n\rangle|^2=|\langle \psi_r,U^{-1}\varphi_n\rangle|^2=|\langle \psi_r,\varphi_{\sigma^{-1}(n)}\rangle|^2}$,

and so the $K$ smallest/largest inner products with $\varphi_n$‘s are $G$-invariant. This means we only need to compute our objective function at $R$ different $\varepsilon$-net points, speeding up our procedure by a factor of $|G|$. As such, this procedure is best suited for $\Phi$‘s which have a large symmetry group.

The magnitude of this speedup is best evaluated in terms of particular groups $G$. To this end, our paper focuses on the group of signed permutation matrices, and we use intuition from Lebesgue integration to construct a $G$-invariant $\varepsilon$-net in which $R$ grows subexponentially with $M$. As an example of how significant this speedup is, we apply our $G$-invariant $\varepsilon$-net to estimate extreme singular values of submatrices of a certain $8\times 560$ matrix. After three minutes of computation in MATLAB (on an old laptop), we are able to establish that every $8\times 404$ submatrix has condition number $\leq 60$. Considering there are a total of $\binom{560}{404}\approx 2.84\times 10^{142}$ such submatrices, this is a particularly significant speedup!

Check out the paper for more details, and for some related research questions posed in the conclusions section.