The 4M-4 Conjecture is False!

Congratulations to Cynthia Vinzant for disproving the 4M-4 conjecture! The main result of her 4-page paper is the existence of a 4\times 11 matrix \Phi such that x\mapsto |\Phi x|^2 is injective modulo a global phase factor (indeed, 11<12=4(4)-4). This is not Cynthia’s first contribution to this problem—her recent paper with Conca, Edidin and Hering proves that the conjecture holds for infinitely many M.

I wanted to briefly highlight the main idea behind this paper: She provides an algorithm that, on input of a 4\times 11 matrix \Phi with complex rational entries, either outputs “not known to be injective” or outputs “injective” along with a certificate of injectivity. The algorithm is fundamentally based on the following characterization of injectivity:

Continue reading The 4M-4 Conjecture is False!

Cone Programming Cheat Sheet

I’m pretty excited about Afonso‘s latest research developments (namely, this and that), and I’ve been thinking with Jesse Peterson about various extensions, but we first wanted to sort out the basics of linear and semidefinite programming. Jesse typed up some notes and I’m posting them here for easy reference:

Many optimization problems can be viewed as a special case of cone programming. Given a closed convex cone K in \mathbb{R}^n, we define the dual cone as

K^*=\{y : \langle x,y\rangle\geq 0~\forall x\in K\}.

Examples: The positive orthant and the positive semidefinite cone are both self-dual, and the dual of a subspace is its orthogonal complement. Throughout we assume we have c\in\mathbb{R}^n, b\in\mathbb{R}^m, closed convex cone K\in\mathbb{R}^n, closed convex cone L\in\mathbb{R}^m, and linear operator A\colon\mathbb{R}^n\rightarrow\mathbb{R}^m. We then have the primal and dual programs

\mbox{(P)} \quad \max \quad \langle c,x\rangle \quad \mbox{s.t.} \quad b-Ax \in L,\quad x \in K

\mbox{(D)} \quad \min \quad \langle b,y\rangle \quad \mbox{s.t.} \quad A^\top y-c\in K^*,\quad y\in L^*

Notice when L and K are both the positive orthant, this is a standard linear program. Further, considering the space of n\times n real symmetric matrices as \mathbb{R}^{n(n+1)/2}, when L=\{0\} and K is the positive semidefinite cone, this is a standard semidefinite program. We consider several standard results (weak duality, strong duality, complementary slackness) in terms of the general cone program.

Continue reading Cone Programming Cheat Sheet

Interviews and offers

I’ve been on the job market full-time for the last 6 weeks or so, and I’ve finally settled on my destination: Starting this August, I’ll be a tenure-track assistant professor at The Ohio State University. My wife and I are very excited to move to Columbus!

Ohio-State-Logo

I wanted to document my process for applying, interviewing and negotiating. I’ll probably refer to this blog post later when I give advice to a future PhD student or postdoc.

1. More offers make a better selection

My goal was to get the most attractive offer possible. Of course, different people have different notions of attractiveness, but there’s still an objective function to optimize. The main point is that you will be more satisfied if there are more options on the table. Not only are you maximizing over a larger set, the offers will compete with each other, and so you can auction for better offers. If you have more than two offers, it might be a little confusing how to maintain the auction — more on that later.

Continue reading Interviews and offers

Alexander Grothendieck

Readers of this blog are probably already aware that Alexander Grothendieck died on Thursday. He is widely regarded as one of the most influential mathematicians in the twentieth century. Since his is not my field of study, I felt that now was a good time to learn a little about why he is so well regarded — I took the day to read a couple of articles from 10 years ago that provide an overview of his life, research, personality, and philosophies. I highly recommend the read: here and here.

Continue reading Alexander Grothendieck

A conditional construction of restricted isometries

I have a recent paper on the arXiv with Afonso Bandeira and Joel Moreira that provides a deterministic RIP matrix which breaks the square-root bottleneck, conditional on a folklore conjecture in number theory.

Here’s the construction (essentially): Let p be a prime which is 1 mod 4. Consider the p\times p DFT matrix, and grab rows corresponding to the quadratic residues (i.e., perfect squares) modulo p. This construction was initially suggested in this paper. We already know that partial Fourier matrices break the square-root bottleneck if the rows are drawn at random, so our result corresponds to the intuition that quadratic residues exhibit some notion of pseudorandomness.

There are actually two folklore conjectures at play in our paper. Conjecture A implies that this matrix breaks the square-root bottleneck, which in turn implies Conjecture B:

Continue reading A conditional construction of restricted isometries

Sparse Representations, Numerical Linear Algebra, and Optimization Workshop

A couple of weeks ago, I attended the “Sparse Representations, Numerical Linear Algebra, and Optimization Workshop.” It was my first time at Banff, and I was thoroughly impressed by the weather, the facility, and the workshop organization. A few of the talks were recorded and are available here. Check out this good-looking group of participants:

groupphoto.sized

I wanted to briefly outline some of the problems that were identified throughout the workshop.

Continue reading Sparse Representations, Numerical Linear Algebra, and Optimization Workshop

An intuition for concentration inequalities

I use concentration inequalities a lot in my research, and it’s about time I write a post about them. Throughout this post, \{X_i\} will denote independent realizations of a common random variable X taking values in the real line. We will take \mu:=\mathbb{E}X<\infty, \sigma^2:=\mathrm{Var}(X)<\infty, and

\displaystyle{\overline{X}_n:=\frac{1}{n}\sum_{i=1}^nX_n.}

The central limit theorem (CLT) essentially states that

\displaystyle{\lim_{n\rightarrow\infty}\mathrm{Pr}\bigg(\big|\overline{X}_n-\mu\big|\geq\frac{t\sigma}{\sqrt{n}}\bigg)=2Q(t)\leq e^{-t^2/2} \qquad \forall t\geq0,}

where the Q-function Q(\cdot) denotes the tail probability of the standard normal distribution. Unfortunately, this only ensures pointwise convergence for each t, meaning CLT provides no uniform tail bound for any fixed n. The purpose of a concentration inequality is to provide such a bound.

Continue reading An intuition for concentration inequalities