AtomicOpt.jl is a Julia package for solving the following non-convex structured optimization problem:

$\text{Find}\enspace x \in \mathbb{R}^n \enspace\text{subject to}\enspace \frac{1}{2}\|Mx - b\|^2 \leq \alpha \enspace\text{and}\enspace rank_{\mathcal{A}}(x) \leq k,$

where $$M:\mathbb{R}^n\to\mathbb{R}^m$$ is a linear operator, $$b\in\mathbb{R}^m$$ is the observation vector, $$\mathcal{A}\subseteq\mathbb{R}^n$$ is the atomic set and $$rank_{\mathcal{A}}(x)$$ measures the complexity of $$x$$ with respect to the atomic set $$\mathcal{A}$$. For example, when $$\mathcal{A}$$ is the set of all signed canonical vectors, i.e.,

$\mathcal{A} = \{\pm e_1, \dots, \pm e_n\},$

then $$rank_{\mathcal{A}}(x)$$ equals to the number of nonzero entries in $$x$$. When $$\mathcal{A}$$ is the set of all normalized rank one matrices, i.e.,

$\mathcal{A} = \{uv^{\intercal} \mid \|u\| = \|v\| = 1\},$

then $$rank_{\mathcal{A}}(x)$$ equals to the rank of the matrix $$x$$. Please see our paper for more detailed discussion on atomic sparsity.