Let $\mathbf{x} \in \mathbb{R}^N$ and $\Phi \in \mathbb{R}^{M \times N}$. Let $\mathbf{y} \in \mathbb{R}^{M}$, where $\mathbf{y} = \Phi \mathbf{x} + \mathbf{w}$ and $\mathbf{w}$ is additive white Gaussian noise.
The LASSO problem can be written as:
\begin{align} \min_{\mathbf{x}} || \mathbf{y} - \Phi \mathbf{x} ||_2^2 + \lambda ||\mathbf{x}||_1 \quad \mbox{subject to} \quad \lambda > 0. \end{align}
The $\ell_1$-norm minimization problem can be written as: \begin{align} \min_{\mathbf{x}} || \mathbf{y} - \Phi \mathbf{x} ||_2^2 \quad \mbox{subject to} \quad ||\mathbf{x}||_1 \le \tau. \end{align}
Are the solutions for the above two convex optimizaton problems the same? If yes, under what conditions are they same.
Yes. The solution for both of the problems are the same. Following is a more general proof:
Let $f$ and $g$ be convex functions, $$\ w_1^*= arg\underset{x}min \ f(x)+\lambda g(x) \quad \mbox{subject to} \quad \lambda > 0 $$ $$\ w_2^*= arg\underset{x}min \ f(x) \quad \mbox{subject to } \ g(x) \leq \tau $$ Writing Lagrangian for the second problem, $$\ \mathcal{L}(x, \lambda) = f(x)+\lambda_L\left(g(x) - \tau \right) \ \text{where } \lambda_L \text{ is the multiplier} $$ From FONC for the second problem, $$\ \nabla \mathcal{L}(w_2^*, \lambda^*) = \nabla f(w_2^*) +\lambda^*\left(\nabla g(w_2^*)\right) = 0 \ \text{where } \lambda^* = 0 \text{ if } g(w_2^*) < \tau $$ For the first problem FONC gives, $$\ \nabla f(w_1^*)+\lambda\left(\nabla g(w_1^*) \right)=0 $$ Since $f$ and $g$ are convex, we can conclude that both solutions are the same for $$\ \tau=g(w_1^*) \text{ and corresponding multiplier } \lambda^*=\lambda $$