Computer Science/Discrete Mathematics Seminar II
Zero-One Rounding of Singular Vectors
Given a matrix $A$, it can be shown that there is a vector $z \in 0,1^n$ for which $|Az|/|Z| \geq |A|_2/C \log(n)$ (a0/1 sum of columns of $A$ which witnesses its large spectral norm) for instance by discretizing the top singular vector of $A$ and taking a dyadic expansion. We give a simple geometric proof of this fact by relating it to the Euclidean diameter of a polytope, and obtain a sharp bound of $|Az| \geq 2|A|_2/\sqrt{\ln(n)}$. We then show that it is possible to extract $k$ orthogonal $0,1$ vectors $z_1, \dotsc, z_k$ such that $|Az_i|/|z_i| \geq \sigma k(A)/\sqrt{k \ln n}$, which is tight up to a $\sqrt{\log k}$ factor, and mention applications to approximating matrices by sums of rectangles.
Joint work with Amit Deshpande and Ravi Kannan.