Analytic expression for the Moreau envelope of $x \mapsto \|Ax\|$

Question

Given an $m \times n$ matrix $A$ and a vector $c \in \mathbb R^n$, define $\eta(A,c) \ge 0$, $$ \eta(A,c) := \sup_{u \in \mathbb R^n} u^\top c - \frac{1}{2}\|u\|^2 - \|Au\|. $$ Note that $\eta(A,c) = \|c\|^2/2 - M_f(c)$, where $M_f(c) := \min_{u \in \mathbb R^n}\dfrac{1}{2}\|u-c\|^2 + \|Au\|$ defines the Moreau envelope of the function $f(x):=\|Ax\|$ at the point $c$.

Question. What is an analytic formula for $\eta(A,c)$, perhaps by means of the singular-values of $A$ ?

(If it helps, it may be assumed that $m=n$ and $A$ is positive-definite).

Upper and lower-bounds

If $\sigma_\min(A)$ is the least singular-value of $A$ and $\sigma_\max(A)$ is its largest singular-value (i.e is operator norm), then, it is clear that $$ \eta(\sigma_\max(A) I_m,c) \le \eta(A,c) \le \eta(\sigma_\min(A) I_m,c). $$

One the other hand, a simple calculation reveals that $\eta(\theta I_m,c) = \dfrac{1}{4}(\|c\|-\theta)_+^2$ for all $\theta \in \mathbb R$. Thus, $$ \frac{1}{4}(\|c\|-\sigma_\max(A))_+ \le \eta(A,c) \le \frac{1}{4}(\|c\|-\sigma_\min(A))_+^2. $$

Answer 1

I have to point out that in most cases, there is no closed-form solution of such problems (say, Moreau-envelope of $\|Ax\|_1$ is also the case), and this can be proved for your case.

Now back to your problem. Let's assume that the SVD decomposition of $A$ is $A=U^\top DV$, where $D$ is a diagonal matrix. Our target problem is: $$ \min_{x} \frac12\|x-c\|^2+\|U^{\top}DVx\| $$ Let $y=Vx$, then this problem is equivalent to: $$ \min_{y} \frac12\|y-Vc\|^2+\|Dy\| $$ Now, we need a simple fact. Assume $a,b\geq0$, then: $$ \sqrt{ab}=\min_{t\geq 0} \frac{a}{2t}+\frac{tb}{2} $$ Using this fact, let's rewrite this problem as: $$ \min_{t\geq 0,y} \frac12\|y-Vc\|^2+\frac{t}{2}\|Dy\|^2+\frac{1}{2t} $$ If you minimize $y$ first, then you can express $y$ in closed-form using parameter $t$: $$ y_i=\frac{(Vc)_i}{D_it+1} $$ If you substitute $y_i$ to the expression, you probably would get: $$ \min_{t\geq 0} \frac12\|Vc\|^2-\sum_i\frac{(Vc)_i^2}{2D_it+1}+\frac{1}{2t} $$ As you can see from this equation, if $D_i$'s are not identitcal, then you would encounter a high-order polynomial, which of course does not admit closed-form solution (and closed-form optimal value) as long as the order succeeds 4.