0
$\begingroup$

In basis Pursuit, L1 minimization is done to perform compressed sensing. In the literature there is a $ \lambda $ parameter used as a regularizer.

What is its significance?

$\endgroup$
2
$\begingroup$

This parameter control sparsity of the basis. Look for articles on L1 norm "oracle property". In essence, by minimizing the L1 norm you're driving your representation to have few non-zero components. The lambda tunes how much of your squared error vs. L1 norm you pay most attention to. Large lambda means you care a lot about sparsity, but not exact matching. Small lambda gives you the opposite. This can also be looked at as a bias-variance tradeoff of your learner.

$\endgroup$
0
$\begingroup$

There are 2 forms of the Basis Pursuit problem:

$$\begin{align*} \text{The $ \lambda $ Form:} & \quad && \arg \min_{x} \frac{1}{2} {\left\| A x - b \right\|}_{2}^{2} + \lambda {\left\| x \right\|}_{1} \\ \text{The $ \epsilon$ Form:} && \quad & \arg \min_{x} {\left\| x \right\|}_{1} \\ & \text{subject to} && \frac{1}{2} {\left\| A x - b \right\|}_{2}^{2} \leq \epsilon \end{align*}$$

Sometimes it is more intuitive to have a look on the $ \epsilon $ form as it tell us exactly the trade off.
The lower $ \epsilon $ it means we require teh solution to hold the Linear Equation and we pay for that with the $ {L}_{1} $ Norm of the solution.

The nice things is that for any value $ \epsilon $ we can find $ \lambda $ for the other form in such way the generate the same solution:

$$ \forall \epsilon, \; \exists \lambda : x \left( \epsilon \right) = x \left ( \lambda \right) $$

Where $ x \left( \epsilon \right) $ and $ x \left ( \lambda \right) $ are the solution of the $ \epsilon $ form and the $ \lambda $ form respectively.

You may see an example in my answer at Cross Validated Question 291962.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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