$\newcommand{\prox}{\operatorname{prox}}$ Consider the function $g(P) = \|PX\|_1$, where $P \in R^m \times R^m$ and $X \in R^m \times R^n$ is a known constant matrix.
In the paper Proximal Algorithms by Parikh and Boyd Moreau decomposition (page 133) is defined as:
$$ v = \prox_f(v) + \prox_{f*}(v) $$
where $f^*(y) = \sup_x(y^Tx - f(x))$
Question 1:
Does it mean that one way to find a proximal operator for $g(P)$ given above is to find:
$$g^*(Y) = \sup_P(Y^TP - \|PX\|_1) = \sup_P\left(Y^TP - \max_{j} \sum_i^m \sum_k^m|p_{ik}x_{kj}|\right)$$
Question 2:
If yes, how it can be found analytically?
My third question refers to their example, given on the page 134; they consider $f = \|\cdot\|$ as some general norm, and by using its dual norm, Moreau decomposition and projection operator:
$$v = \prox_f(v) + \Pi_B(v)$$
where $B = \{x \mid \|x\|_*\le 1\}$, where $\|x\|_*$ is a dual norm.
Question 3:
In our case, however, we do not have a norm operator anymore. Could we still use projection operators? If yes, what should we project on and is it easier to find prox operator this way?
Question 1: No, if you find $g^*(y)$, all you've done is evaluated $g^*(y)$. You have not yet evaluated the prox operator of $g^*$. If you were able to evaluate the prox operator of $g^*$, then the Moreau decomposition would then allow you to evaluate the prox operator of $g$.
Questions 2 and 3: No, I'm pretty sure there is no known analytical expression for the prox operator of $g$ or $g^*$. I think there is no known easy way to compute it (for a general $P$). If there were, we would see it be used often in many important problems where $g$ (with some choice of $P$) appears.