Here's a solution for the specific case where $f(x)=\| x \|_{1}$ and $g(x)=\| y-Ax \|_{2}$. The same appraoch applies to $g(x)=\| A^{T}(y-Ax) \|_{\infty}$.

There are two cases.

If $g(0) \leq s$, then $x^{*}=0$ is feasible for the first problem and because $f(x) > 0$ for all $x \neq 0$, $x^{*}=0$ is the unique optimal solution to the first problem. In that case, let $t=0$. Then $x^{*}=0$ is the only feasible solution to the second problem and thus the unique optimal solution to the second problem.

If $g(0) > s$, then $x=0$ is infeasible for the first problem. Since $x=0$ is the only unconstrained minimum of $f(x)$, any optimal solution to the first problem must have $g(x)=s$. Let $x^{*}$ be an optimal solution to the first problem. Let $t=f(x^{*})$. Clearly, $x^{*}$ is feasible for the second problem. We will show that $x^{*}$ is also optimal for the second problem.

suppose that there is some better solution to the second problem, $\hat{x}$. That is,

$f(\hat{x}) \leq t=f(x^{*})$

and

$g(\hat{x}) < g(x^{*}) = s $

Since $\hat{x}$ is interior to the feasible set for problem one (or simply because $g$ is continuous), we can find an $\epsilon$ with $0 < \epsilon < 1$ and such that

$\tilde{x}=(1-\epsilon)\hat{x}$

has $g(\tilde{x}) \leq s$.

Note that

$f(\tilde{x})=(1-\epsilon)f(\hat{x}) < f(x^{*})$.

This contradicts the assumption that $x^{*}$ was optimal for problem one.

This proof generalizes to any case where $f(x)$ is a vector norm and $g(x)$ is a continuous function.