Bounds on Dimension Reduction in the Nuclear Norm

Oded Regev, Thomas Vidick

For all $n\ge 1$, we give an explicit construction of $m\times m$ matrices $A_1,\dots ,A_n$ with $m=2^{\lfloor n/2\rfloor }$ s…