The k-Support Norm and Convex Envelopes of Cardinality and Rank

Anders Eriksson, Trung Thanh Pham, Tat-Jun Chin, Ian Reid; The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2015, pp. 3349-3357

Abstract


Sparsity, or cardinality, as a tool for feature selection is extremely common in a vast number of current computer vision applications. The $k$-support norm is a recently proposed norm with the proven property of providing the tightest convex bound on cardinality over the Euclidean norm unit ball. In this paper we present a re-derivation of this norm, with the hope of shedding further light on this particular surrogate function. In addition, we also present a connection between the rank operator, the nuclear norm and the $k$-support norm. Finally, based on the results established in this re-derivation, we propose a novel algorithm with significantly improved computational efficiency, empirically validated on a number of different problems, using both synthetic and real world data.

Related Material


[pdf]
[bibtex]
@InProceedings{Eriksson_2015_CVPR,
author = {Eriksson, Anders and Thanh Pham, Trung and Chin, Tat-Jun and Reid, Ian},
title = {The k-Support Norm and Convex Envelopes of Cardinality and Rank},
booktitle = {The IEEE Conference on Computer Vision and Pattern Recognition (CVPR)},
month = {June},
year = {2015}
}