I am starting with a typical $\ell_1$ basis pursuit problem:

$$ \min_{\mathbf{x}} \Vert \mathbf{x} \Vert_1 \quad \mathrm{s.t.} \quad \Vert \mathbf{ERx} - \mathbf{y} \Vert_2 \leq \epsilon, $$

where $\mathbf{R}\in\mathbb{C}^{M \times P}$, and $\mathbf{E}$ is an $M' \times M$ row selection matrix that randomly chooses $M'<P$ rows from $\mathbf{R}$. It is also known that $\operatorname{rank}(\mathbf{ER})=M'$, so that the constraint system is full-rank but under-determined.

Since both $M$ and $P$ are on the order of $10^7$, the above problem is impractical because of memory and computational limitations. An algorithm exists that will let me efficiently compute $\mathbf{R^{\mathrm{H}}}\mathbf{E^{\mathrm{H}}}\mathbf{y}$, so I would like to see if I can combine this with a sparse approximation (described below) to solve the following equivalent problem:

$$ \min_{\mathbf{x}} \Vert \mathbf{x} \Vert_1 \quad \mathrm{s.t.} \quad \Vert \mathbf{R^{\mathrm{H}}}\mathbf{E^{\mathrm{H}}}\mathbf{ERx} - \mathbf{R^{\mathrm{H}}}\mathbf{E^{\mathrm{H}}}\mathbf{y} \Vert_2 \leq \epsilon, $$

Since $\mathbf{E}$ is a row-selection matrix, the product $\mathbf{E^{\mathrm{H}}}\mathbf{E}$ is a diagonal matrix with a $1$ at element $(i,i)$ if row $i$ was selected and $0$ otherwise. Furthermore, given the nature of $\mathbf{R}$, even though the product $\mathbf{R^{\mathrm{H}}}\mathbf{E^{\mathrm{H}}}\mathbf{ER}$ is rather large at $P \times P$, it is also approximately sparse with only a relatively small number of terms with significant modulus per row/column. This makes me think that the above form is doable since I could compute just the sparse approximation and avoid the unrealistic memory and computation requirements.

However, $\mathbf{R^{\mathrm{H}}}\mathbf{E^{\mathrm{H}}}\mathbf{ER}$ has size $P \times P$ but is only of rank $M'$ and this is causing problems with the basis pursuit algorithms as they expect the rows of the constraint matrix to be linearly independent. Hence, my solicitation for input.

Are there any factorizations and/or transformations that could turn the constraints of the second form of the problem into under-determined yet full-rank system? Please do keep in mind the large sizes of these matrices. Any other suggestions/comments are also welcome. We can assume that $\mathbf{R}$ has rank $M$ or $P$, as there is freedom in its design.

  • $\begingroup$ Could you orthogonalise the rows via the Gram-Schmidt algorithm? $\endgroup$
    – Tom Kealy
    Sep 4, 2013 at 9:33
  • $\begingroup$ @TomKealy I might be able to, but then what? I'm not looking for a basis and, unless I am forgetting something, orthogonalizing will change the system. $\endgroup$ Sep 10, 2013 at 16:32
  • $\begingroup$ Just at a glance, I am supposing you already have solutions on the simplest standard Basis Pursuit problem?: $$min |x|, Ax=y$$ or for this?: $$min \mu |x| + ||Ax-y||^2$$ and in the alternative form you exposed?: $$min |x|, ||ERx-y||<=\epsilon$$ Is your scope to propose a new solution of the BP Problem?, or to get solve it and resume your work?. Perhaps a paper reference on this form should be interesting to see. $\endgroup$
    – Brethlosze
    Nov 13, 2016 at 21:41

1 Answer 1


Since $ \epsilon $ is a parameter you need to set, why not trade it with another parameter you need to set to create an easily solvable problem (Relaxation of the Problem)?

You can transform the problem into the following form ($ {L}_{1} $ Regularized Least Squares):

$$ \arg \min_{x} \frac{1}{2} \left\| A x - z \right\|_{2}^{2} + \lambda \left\| x \right\|_{1} $$

There are many solvers for that problem, including the case of large sparse matrices.
For any $ \epsilon $ from the original problem there is $ \lambda $ such that the solutions are the same.
Since $ \epsilon $ it to be arbitrarily set in the original problem you can trade it for $ \lambda $.

This can be solved with many solvers easily without the need for Matrix Inversion.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.