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.

Advertisements

2 thoughts on “Group-theoretic constructions of erasure-robust frames

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s