Codes, Geometry and Random Structures: Day 1

October 24th, 2011 by aram

There is also the promise of an intriguing new additivity violation in the limited-entanglement setting, although I admit that the exact details eluded me.

Yi-Kai Liu,

Universal low-rank matrix recovery from Pauli measurements, based on 1103.2816

Previous work on compressed tomography established that

for any rank-r density matrix $\rho$ , $O(rd \log^2 d)$ random Paulis suffice to reconstruct $\rho$ with high probability.

This work establishes that $O(r d \log^6(d))$ random Paulis work simultaneously for all $\rho$ . This also gives better error bounds for noisy behavior.

As a result, one can obtain bounds on the sample complexity, instead of just the number of measurement settings.

The technical statement that we need is that random Paulis satisfy the following restricted isometry property (RIP):

For all X with rank $\leq r$ ,

$(1-\delta) \|X\|_{S_2} \leq \|R(X)\|_{\ell_2} \leq (1+\delta) \|X\|_2$

Gaussian matrices are known to have this property [Recht, Fazel, Parillo 2007].

More concretely, let $\Omega$ be a random set of $m = O(r d \log^6 d)$ random Pauli matrices.

Define $R(\rho) = ({\rm tr} P\rho)_{P\in \Omega}$ .

Measurements produce $b\approx R(X)$

The reconstruction algorithm is to solve:

${\rm argmin}_{X\geq 0} \|R(X)-b\|_2^2 + \mu {\rm tr} |X|$

Why does this work?

The set of X with ${\rm tr} X \leq 1$ is a ball, and low-rank states are on exposed.

So when we intersect with some generic hyperplane R(X)=b, we’re likely to have a unique solution.

More formally, let $\rho$ be the true state and $S = X-\rho$ . Note that R(S)=0. We want to show S=0. Decompose $S = S_0 + S_c$ , where $S_0$ has rank $\leq 2r$ and $S_c$ has no overlap with row or column spaces of $\rho$ .

If X has minimum trace, then $\|S_c\|_1 \leq \|S_0\|_1$ .

Then we can use RIP to show that $S_0$ and $S_c$ are both small, using a clever telescoping technique due originally to Candes and Recht.

Ok, so how do we prove the RIP? The idea is that R should be well conditioned, and be “incoherent” so that it’s operator norm is much less than its 2-norm.

Recht et al ’07 used a union bound over (a net for) rank-r matrices. This works because Gaussians have great concentration. But Paulis are pricklier.

This work: Use generic chaining (a la Rudelson and Vershynin). This requires proving bounds on covering numbers, which will be done using entropy duality (c.f. Guedon et al 2008).

Here’s a little more detail. If T is a self-adjoint linear map from $M_d$ to $M_d$ , then

define $\|T\|_{(r)} = \sup \{|tr X^\dag T(X)| : X \in U\}$ , where

$U = \{X in M_d : \|X\|_2\leq 1, {\rm rank}(X) \leq r\}$

The goal is to show $\|R*R-I\|_{(r)} \leq 2 \delta - \delta^2$ , where $\delta$ comes from the RIP condition.

The main tool is Dudley’s inequality:

$\mathbb{E}[\sup G(X) : X \in U] \leq {\rm const} \int {\rm d}\epsilon \sqrt{\log(N(U,d_G, \epsilon))}$

Here G is a Gaussian process with $d_G(X,Y) = \sqrt{\mathbb{E}((G(X)-G(Y))^2)}$ and $N(U,d_G,\epsilon)$ is the # of radius- $\epsilon$ balls in metric $d_G$ needed to cover U.

We can upper bound N using the trace norm. Let $B_1$ denote the trace-norm ball.

Define $\|M\|_X = \max_{P \in \Omega} |tr P^\dag M|$ .

There are two estimates of N. The easy one is that

$N(B_1, \|\cdot\|_X, \epsilon) \leq poly(1/\epsilon) \exp(d^2)$

The harder one is that

$N(B_1, \|\cdot\|_X, \epsilon) \leq \exp(\log^2(d) / \epsilon^2)$ .

This is obtained using entropy duality, with arguments that are somewhat specific to the spaces in question, using techniques of Maurey. See paper (and references ) for details.

Matthias Christandl

Page 4 of 5 | Previous page | Next page

Posted in General | 4 comments

Previous post: More live-blogging!
Next post: Codes, Geometry and Random Structures: Day 2