Before revision:  In addition, our hard instance results in new sampling lower bounds for estimating the Ky-Fan Norm, and the cost of  rank-k approximations, i.e. \|A - A_k\|_F^2 = \sum_{i > k \sigma_i^2(A)}  .
After revision:  In addition, our hard instance results in new sampling lower bounds for estimating the Ky-Fan Norm, and the cost of the best rank-k approximations, i.e. \|A - A_k\|_F^2 = \sum_{i > k \sigma_i^2(A)} .