The k-support norm and convex envelopes of cardinality and rank
Files
(Restricted Access)
Date
2015
Authors
Eriksson, A.
Pham, T.
Chin, T.
Reid, I.
Editors
Advisors
Journal Title
Journal ISSN
Volume Title
Type:
Conference paper
Citation
Proceedings / CVPR, IEEE Computer Society Conference on Computer Vision and Pattern Recognition. IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2015, vol.07-12-June-2015, pp.3349-3357
Statement of Responsibility
Anders Eriksson, Trung Thanh Pham, Tat-Jun Chin, Ian Reid
Conference Name
2015 IEEE Conference on Computer Vision and Pattern Recognition (CVPR 2015) (7 Jun 2015 - 12 Jun 2015 : Boston, MA)
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.
School/Discipline
Dissertation Note
Provenance
Description
Access Status
Rights
© 2015 IEEE