AtomicOpt.jl

Julia package for solving the a class of non-convex structured optimization problem.

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.