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

Anders Eriksson, Trung Thanh Pham, Tat-Jun Chin, Ian Reid

CVPR 2015

doi:10.1109/CVPR.2015.7298956 /cvpr/2015/eriksson2015cvpr-ksupport/

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.

PDF CVPR Semantic Scholar

Cite

Text

Eriksson et al. "The K-Support Norm and Convex Envelopes of Cardinality and Rank." Conference on Computer Vision and Pattern Recognition, 2015. doi:10.1109/CVPR.2015.7298956

Markdown

[Eriksson et al. "The K-Support Norm and Convex Envelopes of Cardinality and Rank." Conference on Computer Vision and Pattern Recognition, 2015.](https://mlanthology.org/cvpr/2015/eriksson2015cvpr-ksupport/) doi:10.1109/CVPR.2015.7298956

BibTeX

@inproceedings{eriksson2015cvpr-ksupport,
  title     = {{The K-Support Norm and Convex Envelopes of Cardinality and Rank}},
  author    = {Eriksson, Anders and Pham, Trung Thanh and Chin, Tat-Jun and Reid, Ian},
  booktitle = {Conference on Computer Vision and Pattern Recognition},
  year      = {2015},
  doi       = {10.1109/CVPR.2015.7298956},
  url       = {https://mlanthology.org/cvpr/2015/eriksson2015cvpr-ksupport/}
}