I am solving the basis pursuit problem using CVX and my sensing matrix has grown to about ~10000 x 10000. Naturally, this is a problem with ~10000 unknowns but SeDuMi is really choking on the size. The matrix unfortunately is dense and I do not have a fast operator form. Any ideas how I might run this case and continue to scale to around ~15000 x 15000?
Interior-point methods are not a good choice for large-scale basis pursuit. You should be looking at dedicated first-order solvers like SPGL1 or TFOCS.