Computing the proximal operator of the ℓ₁ induced matrix norm

2020/05/14 by Jérémy E. Cohen, Cohen, Jeremy E.
Computer Science · Mathematics · #Advanced Optimization Algorithms Research #FOS: Mathematics #Iterative Methods for Nonlinear Equations #Matrix Theory and Algorithms #Optimization and Control (math.OC)

paper · pdf · doi:10.48550/arxiv.2005.06804

openalex publication_date 2020/05/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this short article, for any matrix X∈ℝ^{n× m} the proximity operator of two induced norms ‖X‖₁ and ‖X‖_∞ are derived. Although no close form expression is obtained, an algorithmic procedure is described which costs roughly O(nm). This algorithm relies on a bisection on a real parameter derived from the Karush-Kuhn-Tucker conditions, following the proof idea of the proximal operator of the max function found in Parikh(2014).

Related

• The fastest ℓ_1,∞ prox in the west
• A top nine list: Most popular induced matrix norms
• Operator ℓ_p→ℓ_q norms of Gaussian matrices
• Approximation of the Proximal Operator of the ℓ_∞ Norm Using a Neural Network
• The operator (p, q)-norm of some matrices