# Three Paper Announcements

I’ve been pretty busy lately with writing and researching with visitors. These announcements serve as a quick summary of what I’ve been up to:

1. Tables of the existence of equiangular tight frames (with Matthew Fickus). Today, there’s quite a bit known about equiangular tight frames (ETFs), but what is known seems to be scattered across different papers. This paper surveys everything that is known, and tabulates all of the known real and complex ETFs with sufficiently few vectors in sufficiently small dimension. The tables were generated by coding up existence theorems in MATLAB so as to minimize errors. This serves as a “solution” to problem 21 in this documentation of the open problems discussed at the AIM workshop Frame theory intersects geometry. Recently, Matt and I have made a few ETF discoveries with John and Jesse, so you can expect this table to be updated after we announce these discoveries in the coming months.

2. Discrete uncertainty principles and sparse signal processing (with Afonso S. Bandeira and Megan E. Lewis). This paper is based on Megan’s master’s thesis, which I advised. The inspiration for this project came from different uncertainty principles that use the 0-norm (namely, Theorem 1 in Donoho–Stark and Theorem 1.1 in Tao). Unfortunately, since the 0-norm of a vector is integer, it’s not a continuous quantity, and this discontinuity can lead to quasi-paradoxes with uncertainty principles (as we illustrate in the introduction of the paper). As an alternative, we consider a continuous proxy for the 0-norm called numerical sparsity, defined to as $\mathrm{ns}(x):=\|x\|_1^2/\|x\|_2^2$. We derive new uncertainty principles in terms of numerical sparsity and we identify various consequences in sparse signal processing. My favorite consequence is a lower bound on the number of random rows you need from a DFT to make an RIP matrix—the lower bound is $m=\Omega_\delta(k\log n)$, which differs by a log factor from the number of rows used in a Gaussian RIP matrix: $m=O_\delta(k\log(n/k))$.

3. On the tightness of an SDP relaxation of k-means (with Takayuki Iguchi, Jesse Peterson and Soledad Villar). This paper serves as a follow-up to Soledad’s previous paper, which studied a couple different relaxations of the k-means problem. One of the relaxations is formulated as an SDP, and in practice, this relaxation happens to be integral very frequently. The goal is to prove a theorem that explains this phenomenon. Following the strategy in these notes, the main idea is to first show what integrality in the SDP says about the dual certificate (by way of complementary slackness). Unfortunately, complementary slackness in the k-means SDP fails to uniquely determine the dual certificate of an integral solution, and so the researcher needs to make a choice. Soledad’s previous paper made one choice and used it to prove a reasonable guarantee (that the SDP recovers clusters contained in unit balls whose centers are separated by about $2\sqrt{2}$). Our new paper makes a different choice in dual certificate, and our main result gives that the distance can get really close to 2. (This is near-optimal, since recovery is not possible if the distance is less than 2.)