A note on Adrian Lewis' result on permutation invariant functions

Andrew Eberhard, Vera Roshchina

Abstract

We discuss the use of group symmetries in optimization, particularly regarding the structure of subdifferential and projection operators. This work generalizes a classic result of Adrian Lewis—characterizing the subdifferential of a permutation-invariant convex function—to the proximal subdifferential of Schur convex functions invariant under finite reflection groups. We also simplify and generalize results on projections onto symmetric sets, specifically studying projections on sparsity constraints used in sparse signal recovery and compressed sensing.

Introduction

In many optimization problems, the solution is invariant to the ordering or sign of input variables. For instance, the eigenvalues of a matrix or the coefficients of a sparse signal often exhibit such symmetries. In the 1990s, Adrian Lewis established a foundational result in nonsmooth optimization: if a convex function is invariant under permutations, its subdifferential can be characterized by simply reordering coordinates.

However, Lewis’s work was primarily focused on the permutation group and convex functions. This paper addresses two critical gaps: extending these results to more general symmetry groups (like reflections and sign changes) and applying them to non-convex settings, such as the sparsity constraints prevalent in compressed sensing.

The Geometric Framework: Finite Reflection Groups

The authors shift the perspective from simple permutations to the broader framework of Finite Reflection Groups (or Coxeter groups). The central geometric concept is the fundamental chamber.

For any finite reflection group, the space $\mathbb{R}^n$ is partitioned into "chambers" by the reflection planes of the group. Every point $x$ in the space belongs to the orbit of exactly one point $\check{x}$ located within a chosen closed fundamental chamber. This process of mapping $x$ to $\check{x}$ is a generalization of sorting a vector in descending order.

Visualization of a fundamental chamber in a 2D reflection group.

By proving that the intersection of a symmetry orbit and the fundamental chamber is a singleton, the authors establish a unique mapping that simplifies the analysis of symmetric functions.

Key Insights: Subdifferentials and Inner Products

A primary contribution of the paper is the characterization of the proximal subdifferential. The authors show that for a symmetric function, a vector $y$ is a subgradient at $x$ if and only if:

  1. Their "standardized" versions, $\check{y}$ and $\check{x}$, are related in the subdifferential of the restricted function.
  2. The inner product of the original vectors equals the inner product of their standardized versions: $\langle \check{x}, \check{y} \rangle = \langle x, y \rangle$.

This condition ensures that the symmetry of the function is perfectly mirrored in the geometry of its subdifferential.

Applications: Schur Convexity and Sparsity

The framework extends beyond standard convexity to Schur convex functions, which are invariant under the group and respect the "spread" or majorization of their arguments.

One of the most striking results concerns non-convexity. Sparsity constraints (like the $l_0$ "norm") are typically difficult to handle due to their non-convex nature. However, the authors demonstrate that the intersection of a sparsity-constrained set with the fundamental chamber of a "type-2" symmetry group (permutations plus sign changes) is actually convex. This allows complex projections onto symmetric sets to be reduced to simple projections onto linear subspaces within the fundamental chamber.

Conclusion and Future Directions

By utilizing reflection groups, the authors provide a unified geometric root for results in matrix analysis and compressed sensing. While currently limited to finite groups, this work opens the door for future research into continuous symmetries (e.g., $SO(n)$) and the development of specialized numerical solvers that exploit these symmetric projections for faster convergence in high-dimensional optimization.

Summary updated

Abstract

We discuss the use of group symmetries in optimisation, in particular with respect to the structure of subdifferential and projection operators. This allows us to generalise a classic result of Adrian Lewis regarding the characterisation of the subdifferential of a permutation invariant convex function to the characterisation of the proximal subdifferential of a Schur convex function that is invariant with respect to a finite reflection group. We are also able to simplify and generalise results on projections onto symmetric sets, in particular, we study projections on sparsity constraints used in sparse signal recovery and compressed sensing.
BibTeX
@misc{eberhard2014note,
  author = {Andrew Eberhard and Vera Roshchina},
  title = {{A note on Adrian Lewis' result on permutation invariant functions}},
  year = {2014},
  eprint = {1410.7940},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1410.7940},
}
Figure