Orbital Geometry in Optimisation

Andrew Eberhard, Vera Roshchina

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.

Introduction

Many optimization problems possess inherent symmetries. For example, in eigenvalue optimization, the order of eigenvalues does not change the underlying properties of the matrix. Traditionally, researchers handled this using "permutation invariance"—the idea that you can reorder coordinates without changing the function's value. However, permutations are just one specific type of symmetry. This paper identifies a gap: while specific results existed for permutations, there was no generalized, intuitive framework for other types of reflection-based symmetries. By moving to the broader framework of finite reflection groups, we provide a unified geometric toolkit to characterize subdifferentials and projections, offering a cleaner way to solve complex problems in nonsmooth analysis and compressed sensing.

Theoretical Framework: Finite Reflection Groups

The core of this work utilizes the geometry of finite reflection groups (also known as Coxeter groups). The key technical "engine" is the fundamental chamber. Imagine a space divided by mirrors (hyperplanes). A reflection group moves points across these mirrors. The fundamental chamber is a specific wedge of space that contains exactly one representative from every possible "orbit" (the set of all points reachable via symmetry).

Visualization of a fundamental chamber for a 2D reflection group. The shaded wedge represents the unique region containing orbit representatives, bounded by the reflection hyperplanes.

In permutation symmetry, we typically "reorder" coordinates to a non-increasing sequence. In our generalized framework, that concept is replaced by a mapping to the unique point in the fundamental chamber. This allows us to collapse the complexity of the entire space into a single, manageable region.

Subdifferential Characterization

We prove that for a symmetric convex function, a vector is a subgradient if and only if its "chamber representative" is a subgradient of the "chamber representative" of the input, provided a specific inner-product condition is met. We extend these ideas to non-convex functions (specifically Schur convex functions) using proximal subdifferentials, which are essential for modern non-smooth optimization. This generalizes the classic results of Adrian Lewis to a much broader class of symmetries.

Projections and Sparsity Constraints

One of the most practical results of this geometric approach concerns projections onto symmetric sets. We prove that the projection of a point onto a symmetric set is simply the group-transformed projection of its chamber representative.

For sparsity constraints (like the $l_0$ norm), the relevant symmetry is "Type-2" symmetry, which involves both swapping coordinates (permutations) and flipping signs. The fundamental chamber for this group is the set of non-negative, non-increasing vectors. Surprisingly, projections onto certain non-convex symmetric sets (like sparsity constraints) can be treated as projections onto convex sets once the problem is restricted to the fundamental chamber. This provides an explicit, simplified representation for projections onto sparsity constraints ($C_s \cap B$), a major result for researchers building algorithms for sparse signal recovery.

Limitations and Future Work

This work focuses strictly on finite reflection groups. While these cover many practical applications like permutations and sign flips, they do not cover continuous symmetries (such as rotations in $SO(n)$), which would require a different mathematical treatment. Additionally, while we provide the geometric formulas, the computational overhead of finding the group element that maps a point into the fundamental chamber in very high-dimensional spaces remains a topic for further implementation study. Future directions include applying this geometric intuition to derive simpler proofs and new generalizations in more applied areas of signal processing.

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{eberhard2014orbital,
  author = {Andrew Eberhard and Vera Roshchina},
  title = {{Orbital Geometry in Optimisation}},
  year = {2014},
  eprint = {1410.7940},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1410.7940},
}
Figure