Does Matching Pursuit and Soft Thresholding return the same minimizer?

I wanted to understand if the solutions (minimizers) obtained by Matching Pursuit algorithms (say Basis Pursuit denoising) and Soft Thresholding yielded the same minimizer (same solution or same reconstruction).

I am aware that both are sparse inducing algorithms but to my impression it seems they are different and thus should yield different minimizers in general.

Matching Pursuit like algorithms seem to rely on best subset selection based on greedy algorithms that try to solve (approximately) but more directly the true sparse objective:

$$\min_x \| Xw - y \|^2 , \text{ subject to } \| w \|_0 \leq \eta$$

However, L1 regularization via Tikhonov is different to me. It relies on a convex relaxation of the intractable L0 prior:

$$\min_x \| Xw - y \|^2 + \lambda \| w \|_1$$

and then this can be solved via soft thresholding (which if I remember its the same as subgradient descent essentially on the above). Its clear to me that any algorithm that minimizes the Tikhonov formulation (i.e. has L1) must give the same minimizer $x^*$ because the problem is 100% convex and so there is a unique minimizer. So all minimizers to the Tikhonov formulation must be equivalent (wether they are in Lagrangian form or not).

However, since Matching Pursuit doesn't seem to explicitly rely on the L1 formulation but its a greedy algorithm for L0, I'd venture to say they do not return the same solution.

Is this correct?

If there are conditions where they do return the same solution/minimizer (because they satisfy some condition) please point them out if you know them (and if without it they aren't the same, that would be nice to know too).

Yes -- in general Orthogonal Matching Pursuit (or any other local-minimum finding algorithm for the $\ell_0$-problem) will not give the same solution as the $\ell_1$-problem.

That said, we know a very special set of conditions under which two closely related problems have the same solution. If the so-called restricted nullspace property (RNP) applies, then the following two problems have the same solution:

$$\text{arg min}_{\beta} \|\beta\|_0 \text{ such that } y = X\beta$$

and

$$\text{arg min}_{\beta} \|\beta\|_1 \text{ such that } y = X\beta$$

Note that I'm talking about the global solution to these problems being equal. It's easy to get the global solution for the $\ell_1$ problem, but harder to get the global solution for the $\ell_0$ since it's nonconvex. If you want to guarantee that a particular algorithm applied to the $\ell_0$-problem gets the same answer, you typically need stronger conditions. See, e.g., [2] for the case of OMP.

RNP essentially says that there are no vectors in the nullspace of $X$ which decrease the $\ell_1$ norm of the true solution. More precisely, there are no vectors in the nullspace of $X$ which have a lower $\ell_1$-norm off the true support than $\ell_1$-norm on the true support than the "truth." Hence, of the set of vectors which satisfy the constraint, the one with the minimal $\ell_1$ norm is the "truth" and hence is also the solution to the $\ell_0$-problem.

You might ask why we care about the nullspace: it's because if we have any $\hat{\beta}$ which satisfies $y = X\hat{\beta}$ (i.e., is feasible), then any $\hat{\beta} + \beta_{\mathcal{N}(X)}$ (where $\beta_{\mathcal{N}(X)}$ is a vector in the nullspace of $X$) is also feasible (because $X\beta_{\mathcal{N}(X)} = 0$ by definition). Hence, if we assume the true solution is feasible (which it always is in the noiseless model), we only need to show that it minimizes the objective, which is exactly what RNP give us.

Not that this result only applies in the $y = X\beta$ (noiseless)case. If we only require $y \approx X \beta$, the $\ell_1$ and $\ell_0$ cases don't generally coincide. If your $X$ satisfies the RNP but there is noise in your $y$, I'm pretty sure the two solutions ($\ell_1$ and $\ell_0$) will still coincide, but they are no longer guaranteed to be correct. If there is noise, however, you wouldn't typically enforce $y = X\beta$ because that guarantees overfitting.

See Section 10.4 of [1] for details.

A few minor points from your question:

• soft thresholding is not (in general) the solution to the lasso problem (It is when you have orthogonal design $X$); it is associated with the lasso because it is a key component in some (not all) algorithms to solve the lasso problem
• Tikhonov regularization typically only refers to $\ell_2$, not $\ell_1$

[1] Hastie, Tibshirani, and Wainwright. Statistical Learning with Sparsity 2015. CRC Press. Available at https://web.stanford.edu/~hastie/StatLearnSparsity_files/SLS_corrected_1.4.16.pdf

[2] Tropp and Gilbert. "Signal Recovery From Random Measurements Via Orthogonal Matching Pursuit" IEEE Transactions on Information Theory 53(12), 2007. DOI: 10.1109/TIT.2007.909108

• is restricted nullspace property (RNP) the same the restricted isometry property (RIP)? Commented Mar 27, 2018 at 22:06
• See Proposition 10.2 in the book I referenced: RIP implies RNP. Commented Mar 27, 2018 at 22:07
• just to make things 100% clear to me. What you say seems to suggest L1 regularization returns the true sparse solution under RIP/RNP, however, how do you make the connection that OMP does so too (and thus are equivalent under the RIP/RNP)? Commented Mar 27, 2018 at 22:09
• RNP is not enough for OMP to get the true answer. You need a different result from the OMP literature to see when OMP gets the right answer: see, e.g, "Signal Recovery From Random Measurements Via Orthogonal Matching Pursuit" by Tropp and Gilbert (IEEE Transactions on Info. Theory 53(12) 2007). This shows that OMP gets the right answer under a slightly stronger condition called pairwise incoherence, which implies RNP (see Proposition 10.1 in the book I cited). Hence, PI => OMP gets the truth and PI => RNP => L1 gets the truth; put them together to get PI => OMP and L1 get the same answer. Commented Mar 27, 2018 at 22:17
• another thing I noticed is that there is matching pursuit MP, basis pursuit BP, orthogonal basis pursuit OMP, basis pursuit denoising BPDN. BPDN is exactly the same as lasso L1 regularization, thats clear. But the difference between MP, BP and OMP is unclear to me. Do you know the difference? Is MP=BP=OMP and they are just a greedy approximation to the l0 formulation to the problem? Commented Mar 31, 2018 at 19:18