As long as the matrix formed by the x_i satisfies the "restricted isometry property", the optimization problem given by V_V above will recover the optimal solution. For m >> k*log(n), (where in this case m = 10,000, k = 100, and n = 10^6), a random Gaussian matrix will satisfy this property with overwhelmingly large probability. I should probably have checked that the particular numbers I gave will work out, although I'm pretty sure they will, and if not we can replace 10,000 with 20,000 and the point still stands.