Sparse Projection onto Semi-Symmetric Sets with Applications to Sparse Optimization

Abstract Euclidean projection onto the intersection of the sparsity constraint set and an underlying problem-dependent constraint set is an important technique in sparsity or cardinality constrained optimization. When the underlying constraint set is symmetric, it is known that sparse projection can be efficiently computed via a sorting function. Motivated by the observation that some class of underlying constraint sets is partially symmetric, i.e., symmetric with respect to a certain index subset, this paper introduces the notion of semi-symmetry and develops conditions of sparse projection onto a semi-symmetric set. These conditions are characterized by a sorting function and certain combinatorial conditions. When the sparsity level or the number of multi-semi-symmetric index subsets is small or moderate, these conditions can be efficiently verified. Stationary point conditions are obtained for semi-symmetric sets, and the convergence of the projected gradient descent scheme with an improved step length is established in a general setting and is applied to sparse optimization. The proposed semi-symmetric sparse projection based schemes are tested on the joint sparsity and group sparsity problem from statistics and two finance problems subject to semi-symmetric constraints; numerical results demonstrate improved performance in terms of numerical accuracy and computation time.