Euclidean Projections onto Positive and Capped Simplices

About | Installation | Dependencies | Attribution | Contributions | Issues | License | Acknowledgements

About

The s-capped simplex is defined as:

\Delta_{s}^{=} := \{\mathbf{x} \in \mathbb{R}^{n} \mid \mathbf{x}^T\mathbf{1} = s,
 \mathbf{0} \leq \mathbf{x} \leq \mathbf{1} \}

Geometrically, the simplex is a slice at $\mathbf{x}^T\mathbf{1} = s$ of a hypercube $\mathbf{0} \leq \mathbf{x} \leq \mathbf{1}$ shown by the blue region in the image.

Projecting a vector onto a simplex is an important subproblem that appears in imaging, statistics, and machine learning applications 1 2 3. The projection of vector $\mathbf{y}$ onto the simplex amounts to finding a vector $\mathbf{x}*$ that lives in the blue (feasible) region that is closest to y. This vector is the shadow of $\mathbf{y}$. Formally, this projection is written as:

\mathbf{x}^* = proj_{\Delta_{s}^{=}}\left(\mathbf{y}\right) = \underset{x}{\mathrm{argmin}}\{
\frac{1}{2}\|\mathbf{x} - \mathbf{y}\|^2 \mid \mathbf{x} \in
\Delta_{s}^{=}\}

This software computes the projection of vectors onto s-capped and positive simplices (simplices where $\mathbf{x}^*$'s components can be > 1) using sorting methods and fast root finding methods of the Lagrangian's critical points. 2 4.

Example

import numpy as np
from simplexers import capped, positive

rng = np.random.default_rng()
x = rng.uniform(0, 3, size=(4, 100))

# construct capped and positive projections
capped_projection = capped.capped_simplexer(x, s=1, axis=-1)
positive_projection = positive.positive_simplexer(x, s=1, axis=-1)

# validate the sum of each of the 4 vectors is 1
print(np.allclose(np.sum(capped_projection, axis=-1), 1))
print(np.allclose(np.sum(positive_projection, axis=-1), 1))

Installation

Simplexers is available on pypi for easy intallation into virtual environments.

Python Virtual Environment

1. Create your virtual environment, Here we name it my_venv.

$ python3 -m venv my_venv

2. Activate your 'my_venv' environment

$ source my_venv/bin/activate

3. Install openseize into your virtual environment

(my_venv)$ pip install simplexers

Conda Virtual Environment

1. Download the simplexers environment configuration yaml

2. Create a conda simplexers environment.

$ conda env create --file environment.yml

3. Activate the simplexers environment.

$ conda activate simplexers

From Source

To get the development version:

1. Create a virtual environment with latest pip version.

$ python3 -m venv env
$ source env/bin/activate
$ pip install --upgrade pip

2. Get the source code

$ git clone https://github.com/mscaudill/simplexers.git

3. CD into the directory containing the pyproject.toml and create an editable install with pip using the development dependencies

$ pip install -e .[dev]

Dependencies

Simplexers requires Python ≥ 3.10 and has the following dependencies:

package	pypi	conda
numpy	https://pypi.org/project/numpy/	✓
scipy	https://pypi.org/project/scipy/	✓
ipython	https://pypi.org/project/ipython/	✓
notebook	https://pypi.org/project/jupyter/	✓

Attribution

Please see the Cite this repository under the About section or the citation file.

Contributions

Contributions are what makes open-source fun and we would love for you to contribute. Please check out our contribution guide to get started.

Issues

Simplexers provides custom issue templates for filing bugs, requesting feature enhancements, suggesting documentation changes, or just asking questions. You can file an issue here.

License

Simplexers is licensed under the terms of the 3-Clause BSD License.

Acknowledgements

This work is generously supported through the Ting Tsung and Wei Fong Chao Foundation