Random Matrices: l1 Concentration and Dictionary Learning with Few Samples

Let X be a sparse random matrix of size n × p (p ≫ n). We prove that if p ≥ Cn log⁴ n, then with probability 1 - o(1), ∥X^T v∥₁ is close to its expectation for all vectors v ∈ Rⁿ (simultaneously). The bound on p is sharp up to the polylogarithmic factor. The study of this problem is directly motivated by an application. Let A be an n×n matrix, X be an n×p matrix and Y = AX. A challenging and important problem in data analysis, motivated by dictionary learning and other practical problems, is to recover both A and X, given Y . Under normal circumstances, it is clear that this problem is underdetermined. However, in the case when X is sparse and random, Spielman, Wang and Wright showed that one can recover both A and X efficiently from Y with high probability, given that p (the number of samples) is sufficiently large. Their method works for p ≥ Cn² log² n and they conjectured that p ≥ Cn log n suffices. The bound n log n is sharp for an obvious information theoretical reason. The matrix concentration result verifies the Spielman et. al. conjecture up to a log³ n factor. Our proof of the concentration result is based on two ideas. The first is an economical way to apply the union bound. The second is a refined version of Bernstein´s concentration inequality for a sum of independent variables. Both have nothing to do with random matrices and are applicable in general settings.