Skip to main content

Questions tagged [proximal-operators]

Use this tag in question related to the Proximal Operator / Proximal Mapping. It might also be used in question about Proximal Gradient Method and Alternating Direction Method of Multipliers (ADMM).

Filter by
Sorted by
Tagged with
0 votes
0 answers
27 views

Proximal point operator of maximum of functions

I want to know whether the proximal point operator of a function with a special structure can be expressed in terms of simpler proximal point operators. Setup: For a proper, convex and lower ...
AverageJoe's user avatar
-1 votes
0 answers
16 views

Proximal point method in convex-concave saddle point problem

how to verify: the proximal point method generates the iterate $\{x_{k+1} , y_{k+1}\}$ which is defined as the unique solution to the saddle point problem is the solution of problem $$\min_{x\in\...
thelittleprincess's user avatar
1 vote
0 answers
33 views

Proximal operator of conjugate of Euclidean norm

I am trying to solve the following problem: Given $\tau \in \mathbb{R}_{++}, \rho \in \mathbb{R}_{++},~y_n \in \mathbb{R}^n,~z_n \in \mathbb{R}^n$. Derive $$\text{prox}_{\frac{1}{\tau} g^{*}} (y_n + \...
PT_98's user avatar
  • 11
0 votes
0 answers
12 views

Results on convergence and runtime rates of proximal algorithms

Are there any known results on the convergence rates and computational runtime of proximal algorithms? I'm interested in finding out how well they scale with increasing number of input dimensions, but ...
Sparsity's user avatar
  • 119
0 votes
0 answers
48 views

Same result in every iterations from subgradient and proximal gradient method.

I'm trying to implement the subgradient method and proximal gradient method with constant stepsize for the lasso problem but the result for the subgradient method and proximal gradient is almost ...
Help me pls's user avatar
0 votes
0 answers
29 views

Manipulating a linear form into a proximal operator form

Given an expression: $$\arg\min_x -\alpha p^TAx + f(x)$$ I'd like to define $v$ such that: $$\text{prox}_{\sigma f}(v) = \arg\min_x 0.5 \|x - v\|_2^2 + \sigma f(x) = \arg \min_x -\alpha p^TAx + f(x)$$ ...
Eric Johnson's user avatar
0 votes
0 answers
118 views

Proof for basic properties of proximal operators

I am reading the paper "Proximal algorithms" by N. Parikh and S. Boyd, and I found interesting the basic properties of proximal operators. However, I can't prove the equivalence for the ...
Emmanuel Martínez's user avatar
0 votes
1 answer
99 views

To prove an inequality related to the proximal operator (or non-expensive operator)

I am seeking assistance in proving an inequality that I believe holds for a specific mathematical concept involving the proximal operator based on a proper convex function. The inequality is as ...
littlepepper's user avatar
3 votes
1 answer
127 views

Directional derivative of proximal mapping of a convex function

Let $f:\mathbb{R}^n\rightarrow\overline{\mathbb{R}}$ be a proper closed convex function that is locally Lipschitz continuous on its domain $D(f)$. Define the proximal mapping of $f$ to be $$\textbf{...
William's user avatar
  • 997
0 votes
1 answer
89 views

coerciveness of $\|Hx - y\|_2^2 + R(x)$ where $R$ convex

Let $x \in \mathbb{R}^d$, $y \in \mathbb{R}^m$, $H \in \mathbb{R}^{m,d}$ and $R$ proper, convex and lower-semicontinuous. What do we require $H$ to fulfill in order for $$x \mapsto \|Hx - y\|_2^2 + R(...
Pazu's user avatar
  • 1,097
0 votes
0 answers
27 views

is a function which all stationary points are global minima prox-regular for some $\alpha$>0?

Let $f$ be a function which all stationary points are global minima. This type of functions are also known as invex. It means, there exits $\eta(x,y)$ such that $f(x)-f(y) \geq \zeta_{y}^{T}\eta(x,y)$ ...
samuel pinilla's user avatar
5 votes
1 answer
105 views

Proximal operator of squared $\ell_1$-norm

For any $a \in \mathbb R^d$ and $t \ge 0$, let $p_t(a)$ be the unique minimizer of $f_t(x;a) := \|x-a\|_2^2 + t\|x\|_1^2$ over $x \in \mathbb R^d$. Question. Is there an analytic formula for $p_t(a)$ ?...
dohmatob's user avatar
  • 9,575
1 vote
0 answers
72 views

Proximal operator of the $L^1$ norm, constrained to $x\ge0$

A standard variational problem (arising, e.g., in imaging) reads $$ \operatorname{argmin}_x \frac{1}{2}\Vert Ax - y\Vert ^2 + \Vert x\Vert_1 $$ where the $1$-norm serves as a sparsifying regularizer. ...
rod's user avatar
  • 779
0 votes
0 answers
49 views

Inexact ADMM without over-relaxation

Let f$,g$ be proper closed convex functions, $u=(y,z)$, and the problem: $$ \begin{equation} \begin{split} \min_{x,u} \ &f(x) + g(u) \\ \text{s.t. } & Ax + Bu = c \end{split} \end{equation} $$ ...
Hugo B's user avatar
  • 15
2 votes
0 answers
93 views

The Sub Gradient and the Proximal Operator of ${L}_1$ Norm with Metric

I want to solve the optimization: $$\arg\underset{x}{\min}f(x) = \arg\underset{x}{\min}\lambda\lVert Mx\rVert_1 + \frac{1}{2}\lVert x-y\rVert_2^2$$ Where $x,y\in\mathbb{R}^{n}$ and $M\in\mathbb{R}^{n\...
zytadam's user avatar
  • 21
0 votes
0 answers
67 views

Optimization with positive definite constraint

I am trying to solve for a given $Z$ and $\mu, \lambda > 0$: $$d(Z) = \min_{X \succ 0, Y} \left\{ - \log \det(X) + \langle S, X \rangle + \lambda \sum_{i \neq j} |Y_{ij}| + \frac{\mu}{2} ||Y||_F^2 +...
np-hard's user avatar
  • 137
0 votes
0 answers
114 views

Matrix completion with proximal gradient method

I am trying to solve the matrix completion problem with proximal gradient method: $$\min_{||X||_* \leq \theta} \frac{1}{2}\sum_{(i, j) \in \Omega} (X_{ij} - M_{ij})^2$$ or in terms of the projection ...
np-hard's user avatar
  • 137
1 vote
2 answers
202 views

The existence of proximal operator

My problem: Consider a nonempty closed convex set $C \subset \mathbb{R}^n$ and a continuous convex function $f: \mathbb{R}^n \rightarrow \mathbb{R}$. For $x \in \mathbb{R}^n$, we define $\Phi_{f, x} \...
Pipnap's user avatar
  • 431
0 votes
1 answer
102 views

Jacobian of Proximal Operator is Positive Semidefinite

I have been reading a paper involving the following proximal operator $\hat{y}:R^{p} \to R^p$: $$\hat{y}(v) := \text{argmin}_{\beta \in {R}^{p}} \left\{\frac{1}{2} \|v - \beta\|_2^2 + \theta \|\Sigma^{...
XiaoHei's user avatar
  • 97
2 votes
1 answer
122 views

Proximal Gradient Descent on Generalized Lasso Problem?

I'm trying to run proximal gradient descent on the following problem: $$min_u \frac{1}{2} ||u-z||_2^2 + \lambda |Du|$$ where $|Du| = \sum_{i=1}^{N-1} |u_{i+1} - u_i| $ I've come up with the dual ...
skidjoe's user avatar
  • 365
1 vote
1 answer
744 views

Example for closed proper convex function

I have been self-studying Proximal Algorithms by Neal Parikh and Stephen Boyd. It provides a definition of closed proper convex functions without any examples. The definition is given below. Convex ...
XiaoHei's user avatar
  • 97
0 votes
0 answers
84 views

Least-squares optimization with $\ell_2$ and (negative) $\ell_1$ regularization

I want to solve the following optimization problem: $$\mathop{\operatorname{arg\,min}}\limits_x \|y-Ax\|_2^2 + \lambda \|x\|_2^2 - \lambda \cdot 2c \cdot \|x\|_1$$ My idea was to use a proximal ...
refle's user avatar
  • 123
2 votes
0 answers
187 views

Proximal operators contractive with arbitrary norms

The proximal point operator for a convex function $f:\mathbb{R}^D\rightarrow \mathbb{R}$ can be defined to be $$ \operatorname{prox}_{\lambda f}(v)=\underset{x}{\operatorname{argmin}}\left(f(x)+\frac{...
ntrstd11's user avatar
  • 239
1 vote
0 answers
183 views

Proximal operator of the addition of a quadractic term and Lasso penalty

I am trying to derive the proximal operator $\operatorname{prox}_{\lambda}f(v), v \in \mathbb R^n$ of the addition between a quadratic term and a lasso penalty $f(x) = \lVert b - Ax \rVert_2^2 + \tau \...
user418560's user avatar
1 vote
0 answers
105 views

When is proximal gradient descent better than projected gradient descent?

Suppose one is given two optimization problems ($P_1$ and $P_2$ respectively): $$ \min_{z\in \mathbb R^n} \left\{\frac{1}{2} \|b - Az\|_2^2 + \iota_{\mathcal{C}}(z)\right\} \\ \min_{z\in \mathbb R^n} \...
bashfuloctopus's user avatar
1 vote
1 answer
168 views

Correct cases for proximal operator of $L_2$ / Euclidean norm when solving without Moreau's decomposition

For the preparation of my lecture, I'm trying to derive the proximal operator for the $L_2$-norm, i.e., the solution of: $$ \hat{\mathbf{x}}(\mathbf{y}) = \underset{\mathbf{x}}{\text{arg min}}\quad \...
jojomey's user avatar
  • 11
3 votes
0 answers
84 views

Whats the idea behind using Bregman divergence (in particular Bregman proximal method) to minimise a functional?

Given some functional $E$ on a convex set $\Omega$, the Bregman divergence $D_E$ (of some convex function $E$) is defined at a point $p$ as the difference between its value at that point and its first ...
Monty's user avatar
  • 2,320
1 vote
0 answers
47 views

Proximal operator for ratio of $\ell_1$, $\ell_2$ norms

I'm interested in computing the proximal operator for the ratio of $\ell_1, \ell_2$ norms $$ \text{prox}_{\ell_1/\ell_2}(x) = \arg\min_{z} \frac{1}{2}\|z-x\|^2 + \frac{\|z\|_1}{\|z\|_2}. $$ Does this ...
v1105's user avatar
  • 143
5 votes
0 answers
218 views

Convergence of Proximal Gradient Descent

1. Background of Proximal Gradient Descent I am studying and using Proximal Gradient Descent (PGD) to solve the following vector optimization problem: $$ \hat{\mathbf{x}}=\underset{{\mathbf{x}}}{\arg\...
BinChen's user avatar
  • 628
1 vote
0 answers
75 views

Primal updates for augmented Lagrangian in ADMM

I am reading this tutorial that uses ADMM: https://waller-lab.github.io/DiffuserCam/tutorial/algorithm_guide.pdf The objective function that needs to be minimized and the augmented Lagrangian is ...
A Khan's user avatar
  • 21
0 votes
0 answers
421 views

Proximal operator for an $L$-smooth but nonconvex function

Proximal operator definition is: \begin{align} \operatorname{prox}_{\eta f}(x) := \arg\min_{z} \ \eta f(z) + \frac{1}{2}\| z - x \|_2^2, \end{align} where typically $f$ is assumed to be closed convex ...
user550103's user avatar
  • 2,688
1 vote
1 answer
47 views

$l_1$ and $l_2$ norm minimization with a constraint

While working on the algorithm, I need to solve the following problem $$ \min_{x \in \mathbb{R}^n} \| x \|_1 + \frac{\alpha}{2}\| x - y \|^2 \\ \mathrm{s.t.} \ \| x - s \|^2 \le r$$ where $y,s \in \...
nokatan's user avatar
  • 11
2 votes
1 answer
940 views

The Proximal (Prox) Operator of the $ {L}_{0} $ Pseudo Norm Function

What is the Proximal Operator ($ \operatorname{Prox} $) of the Pseudo $ {L}_{0} $ Norm? Namely: $$ \operatorname{Prox}_{\lambda {\left\| \cdot \right\|}_{0} } \left( \boldsymbol{y} \right) = \arg \...
Royi's user avatar
  • 8,974
0 votes
1 answer
96 views

How to derive the proximal operator for a squared error

To derive the proximal operator of $f=\frac{1}{2} \Vert x \Vert_2^2$: $\mathbb{prox}_{\lambda f}(x)=\left(\frac{1}{1 + \lambda} \right) x$ following, what is the proximal operator of the squared error ...
Dr. Zezo's user avatar
  • 109
0 votes
1 answer
59 views

Encoding line search condition into the proximal gradient subproblem

Given a convex function $f$, we often want to solve the problem like $$\inf_{x \in A} f(x),$$ for some convex feasibility set $A$. With the starting point $x \in A$, we can approximate the gradient $\...
The One's user avatar
  • 834
1 vote
0 answers
115 views

Optimality condition of proximal gradient

Given a convex $L$-smooth function $g: \mathbb{R}^d \rightarrow \mathbb{R}$ and a differentiable convex function $h: \mathbb{R}^d \rightarrow \mathbb{R}$ I want to find the optimality condition of the ...
Iyad  Walweel's user avatar
1 vote
1 answer
604 views

Proximal Gradient Descent

I am trying to solve the below optimization problem using proximal gradient descent on a dataset in python: $f(\theta) = \arg\min_{\theta \in R^d}\frac{1}{m}\sum_{i=1}^m\Big [log(1+exp(x_i\theta))-...
user15084764's user avatar
1 vote
0 answers
238 views

What is proximal operator of nuclear norm in weighted space? (variable metric)

I am trying to find out proximal operator of nuclear norm in weighted space. First, proximal operator of nuclear norm is $$\text{prox}_{\lambda | \cdot |_*}(A) = \arg\min_X \frac{1}{2}\|X-A\|_F^2 + \...
HHSS's user avatar
  • 11
2 votes
0 answers
197 views

Proximal operator of the difference of negative entropy and squared norm

Let $\lambda >0$. I am looking for an analytic expression of \begin{equation} \mathrm{prox}_{\lambda\psi} (x), \end{equation} where $\mathrm{prox}$ denotes the proximal operator, and $\psi \colon \...
galoupi's user avatar
  • 21
2 votes
0 answers
154 views

Finding proximal operator of the distance function to a closed convex set

Given a closed convex set $C \subset E$ (Euclidean space contained in $\mathbb{R}^n$). Prove that $$\text{prox}_{d_C}(x) = x+\min\left\{\dfrac{1}{d_C(x)}, 1\right\}(P_C(x)-x),$$ where $d_C$ is the ...
ohana's user avatar
  • 873
2 votes
0 answers
119 views

Proof that the difference between the input and output of the proximal operator belongs to the subdifferential

The proximal operator $\text{prox}$ is defined as follows, for a function $f$, at point $x$: $$\text{prox}_f(x) = \underset{u}{\text{argmin}} (f(u) + \frac{1}{2} ||x-u||^2)$$ The subdifferential $\...
David Cian's user avatar
2 votes
2 answers
114 views

Why does $f:\mathbb{R}^n\rightarrow\mathbb{R}\cup\{\infty\}$ closed, proper, convex imply that $f(x)+\|Ax-b\|^2$ attains a minimum?

I'm currently reading the paper "Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers" by Boyd et al. about the alternating direction method ...
cfunky's user avatar
  • 43
1 vote
0 answers
361 views

Proof for the orthogonal projection onto the L-infinity $L_{\infty}$ norm ball for the complex-valued

Problem: Prove orthogonal projection onto the $L_{\infty}$ norm ball, for $x \in \mathbb{C}^N$ and $\eta \geq 0$, is \begin{align} P_{B_{\| \cdot \|_{\infty} \leq \eta}} &= \left[\operatorname{...
learning's user avatar
  • 691
1 vote
0 answers
73 views

Connection between proximal mapping and strong convexity

I need some helps to solve this proof, any guidance will be greatly appreciated. Suppose $\mathbf{x}_k$=$Prox_{\eta}\,g(\mathbf{y}_k-\eta\nabla f(\mathbf{y}_k))$, prove that: \begin{align*} g(\mathbf{...
Migolas's user avatar
  • 59
0 votes
0 answers
299 views

Proximal operator of squared Euclidean distance to a set, i.e., $\operatorname{dist}\left(\right)$

Could anyone please help me to prove that a proximal operator of squared Euclidean distance to a set $\mathcal{C}$ is $$\operatorname{prox}_{t\operatorname{dist}^2}\left(x\right) = \frac{1}{(t+1)} \...
user550103's user avatar
  • 2,688
1 vote
0 answers
132 views

How can I solve the large scale convex optimization problem?

I have a large scale convex optimization problem as the following shows. $$\begin{array}{ll} \underset{\mathbf{x} \in \mathbb{R}^K}{\text{minimize}} & -\alpha^T[\mathrm{ln}(\mathbf{1}+\mathbf{x})-\...
Soven's user avatar
  • 31
0 votes
0 answers
326 views

Proximal operator intuition

I'm studying proximal operators. But there is something that disturbs me quite a lot and can't find an answer to it. If ℎ is a closed convex function, then the proximal operator of ℎ (with parameter 𝑡...
RFTexas's user avatar
  • 414
2 votes
2 answers
641 views

Proximal Point of the absolute value function

Absolute value function is defined as follows: \begin{equation*} f(x) = |x| = \left\{ \begin{array}{ll} x & \mbox{if } x \geq 0 \\ -x & \mbox{if } x < 0 \end{array} \right. \end{...
Umar's user avatar
  • 31
1 vote
0 answers
63 views

Different definitions of the proximal map? What is going on here

I am really confused about the proximal operator. My teacher has lectured and posted notes where she defines the proximal operator like this: I am trying to get some intuition for this weird function....
Karagounis Z's user avatar
3 votes
0 answers
145 views

Proximal operator of the function $w \mapsto \max_{i=1}^k a_i^Tw$, for fixed $a_1,\ldots,a_k \in \mathbb R^n$

Let $a_1,\ldots,a_k \in \mathbb R^n$ and consider the convex function $F:\mathbb R^n \to \mathbb R$ defined by $F(w) := \max_{i=1}^k a_i^\top w $. Question. What is the proximal operator of $F$ ? ...
dohmatob's user avatar
  • 9,575