A convex method for learning d-valued models

Learning structurally constrained models such as sparse or group-sparse vectors, low-rank matrices, etc. is an important topic in machine learning. In this work, we consider vectors with only a few distinct values which we call d-valued vectors. This structure is useful when there are relations between the covariates in a regression task, or similarity between features in a classification problem. We introduce the d-variation norm as a penalty to promote this structure, and obtain useful optimization tools for this norm, such as its proximal operator, computed by solving a convex quadratic program. Some extensions such as matrix norms have been presented. The usage of this norm in a classification problem has been exemplified.