__
TR16-093 | 4th June 2016 01:28
__

#### Bounded Matrix Rigidity and John's Theorem

**Abstract:**
Using John's Theorem, we prove a lower bound on the bounded rigidity of a sign matrix, defined as the Hamming distance between this matrix and the set of low-rank, real-valued matrices with entries bounded in absolute value. For Hadamard matrices, our asymptotic leading constant is tighter than known results by a factor of two whenever the approximating matrix has sufficiently small entries.