A few paper announcements

This last semester, I was a long-term visitor at the Simons Institute for the Theory of Computing. My time there was rather productive, resulting in a few (exciting!) arXiv preprints, which I discuss below.

1. SqueezeFit: Label-aware dimensionality reduction by semidefinite programming.

Suppose you have a bunch of points in high-dimensional Euclidean space, some labeled “cat” and others labeled “dog,” say. Can you find a low-rank projection such that after projection, cats and dogs remain separated? If you can implement such a projection as a sensor, then that sensor collects enough information to classify cats versus dogs. This is the main idea behind compressive classification.

Advertisements

Partisan gerrymandering with geographically compact districts

The following tweet has been making the rounds on social media:

If yesterday's Alabama Senate race had been a House election, the Republicans, who got *fewer* votes, would have won 6 out of 7 seats, and the Democrats, who *won* the vote statewide, only 1 out of 7. That's how gerrymandered Alabama is. pic.twitter.com/asGex1KAIC

— Leonardo Carella (@leonardocarella) December 13, 2017

Notice that since the Democrats won overall, it would be impossible for Republicans to win all seven districts, no matter how the map was drawn. As such, you might say that Alabama has been gerrymandered as effectively as possible. Sure enough, you can find the usual tell-tale signs of gerrymandering: Some of the district boundaries exhibit strange jagged portions — these portions undoubtedly maneuver to include some parts of the map while avoiding others.

An impossibility theorem for gerrymandering

I just posted my latest paper on the arXiv, this one co-authored with Boris Alexeev. In this paper, we study a new technique that is currently being reviewed by the Supreme Court to detect unconstitutional gerrymandering. Recall that gerrymandering refers to the process whereby electoral district boundaries are manipulated in order to reduce or increase the voting power of a certain group of people. Gerrymandered districts are frequently detected by their bizarre shape. Here are some noteworthy examples (from Wikipedia):

Last year, the Supreme Court found NC-1 and NC-12 (the first two districts above) to be the result of unconstitutional racial gerrymandering. We’ll discuss IL-4 (the district on the right) later.

Monte Carlo approximation certificates for k-means clustering

This week, I visited Afonso Bandeira at NYU to give a talk in the MaD seminar on the semidefinite relaxation of k-means. Here are the slides. The last part of the talk is very new; I worked it out with Soledad Villar while she visited me a couple weeks ago, and our paper just hit the arXiv. In this blog entry, I’ll briefly summarize the main idea of the paper.

Suppose you are given data points , and you are tasked with finding the partition that minimizes the k-means objective

(Here, we normalize the objective by for convenience later.) To do this, you will likely run MATLAB’s built-in implementation of k-means++, which randomly selects of the data points (with an intelligent choice of random distribution), and then uses these data points as proto-centroids to initialize Lloyd’s algorithm. In practice, this works very well: After running it a few times, you generally get a very nice clustering. But when do you know to stop looking for an even better clustering?

Optimal line packings from finite group actions

Joey Iverson recently posted our latest paper with John Jasper on the arXiv. This paper can be viewed as a sequel of sorts to our previous paper, in which we introduced the idea of hunting for Gram matrices of equiangular tight frames (ETFs) in the adjacency algebras of association schemes, specifically group schemes. In this new paper, we focus on the so-called Schurian schemes. This proved to be a particularly fruitful restriction: We found an alternate construction of Hoggar’s lines, we found an explicit representation of the “elusive” packing from the real packings paper (based on a private tip from Henry Cohn), we found an packing involving the Mathieu group (this one beating the corresponding packing in Sloane’s database), we found some low-dimensional mutually unbiased bases, and we recovered nearly all small sized ETFs. In addition, we constructed the first known infinite family of ETFs with Heisenberg symmetry; while these aren’t SIC-POVMs, we suspect they are related to the objects of interest in Zauner’s conjecture (as in this paper, for example). This blog entry briefly describes the main ideas in the paper.

Optimal line packings from association schemes

Joey Iverson recently posted our paper with John Jasper on the arXiv. As the title suggests, this paper explains how to construct optimal line packings (specifically, equiangular tight frames) using association schemes. In particular, we identify many schemes whose adjacency algebra contains the Gram matrix of an ETF. This unifies several existing constructions, and also enabled us to construct the first known infinite family of ETFs that arise from nonabelian groups.

John is on the job market this year, and when reading his research statement, I was struck by his discussion of our paper, so I asked him to expand his treatment to a full blown blog entry. Without further ado, here is John’s guest blog post (which I’ve lightly edited for hyperlinks and formatting):

Recent developments in equiangular tight frames, II

Equiangular tight frames (ETFs) are optimal packings of lines through the origin. At the moment, they are the subject of a rapidly growing literature. In fact, there have been quite a few updates since my last post on this subject (less than five months ago), and I’ve revamped the table of ETFs accordingly. What follows is a brief discussion of the various developments:

1. There is an ETF of 76 vectors in

See this paper. Last time, I mentioned a recent proof that there is no ETF of 76 vectors in . It turns out that a complex ETF of this size does exist. To prove this, it actually seems more natural to view the vectors as columns of a matrix whose row vectors sum to zero. As a lower-dimensional example, consider the following matrix: