nips nips2012 nips2012-133 nips2012-133-reference knowledge-graph by maker-knowledge-mining

133 nips-2012-Finding Exemplars from Pairwise Dissimilarities via Simultaneous Sparse Recovery


Source: pdf

Author: Ehsan Elhamifar, Guillermo Sapiro, René Vidal

Abstract: Given pairwise dissimilarities between data points, we consider the problem of finding a subset of data points, called representatives or exemplars, that can efficiently describe the data collection. We formulate the problem as a row-sparsity regularized trace minimization problem that can be solved efficiently using convex programming. The solution of the proposed optimization program finds the representatives and the probability that each data point is associated with each one of the representatives. We obtain the range of the regularization parameter for which the solution of the proposed optimization program changes from selecting one representative for all data points to selecting all data points as representatives. When data points are distributed around multiple clusters according to the dissimilarities, we show that the data points in each cluster select representatives only from that cluster. Unlike metric-based methods, our algorithm can be applied to dissimilarities that are asymmetric or violate the triangle inequality, i.e., it does not require that the pairwise dissimilarities come from a metric. We demonstrate the effectiveness of the proposed algorithm on synthetic data as well as real-world image and text data. 1


reference text

[1] S. Garcia, J. Derrac, J. R. Cano, and F. Herrera, “Prototype selection for nearest neighbor classification: Taxonomy and empirical study,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 34, no. 3, pp. 417–435, 2012.

[2] L. Kaufman and P. Rousseeuw, “Clustering by means of medoids,” In Y. Dodge (Ed.), Statistical Data Analysis based on the L1 Norm (North-Holland, Amsterdam), pp. 405–416, 1987.

[3] M. Gu and S. C. Eisenstat, “Efficient algorithms for computing a strong rank-revealing qr factorization,” SIAM Journal on Scientific Computing, vol. 17, pp. 848–869, 1996.

[4] B. J. Frey and D. Dueck, “Clustering by passing messages between data points,” Science, vol. 315, pp. 972–976, 2007.

[5] J. A. Tropp, “Column subset selection, matrix factorization, and eigenvalue optimization,” ACM-SIAM Symp. Discrete Algorithms (SODA), pp. 978–986, 2009.

[6] C. Boutsidis, M. W. Mahoney, and P. Drineas, “An improved approximation algorithm for the column subset selection problem,” in Proceedings of SODA, 2009, pp. 968–977.

[7] E. Elhamifar, G. Sapiro, and R. Vidal, “See all by looking at a few: Sparse modeling for finding representative objects,” in IEEE Conference on Computer Vision and Pattern Recognition, 2012.

[8] J. Bien, Y. Xu, and M. W. Mahoney, “CUR from a sparse optimization viewpoint,” NIPS, 2010.

[9] T. Chan, “Rank revealing QR factorizations,” Lin. Alg. and its Appl., vol. 88-89, pp. 67–82, 1987.

[10] L. Balzano, R. Nowak, and W. Bajwa, “Column subset selection with missing data,” in NIPS Workshop on Low-Rank Methods for Large-Scale Machine Learning, 2010.

[11] E. Esser, M. Moller, S. Osher, G. Sapiro, and J. Xin, “A convex model for non-negative matrix factorization and dimensionality reduction on physical space,” IEEE Transactions on Image Processing, vol. 21, no. 7, pp. 3239–3252, 2012.

[12] M. Charikar, S. Guha, A. Tardos, and D. B. Shmoys, “A constant-factor approximation algorithm for the k-median problem,” Journal of Computer System Sciences, vol. 65, no. 1, pp. 129–149, 2002.

[13] B. J. Frey and D. Dueck, “Mixture modeling by affinity propagation,” Neural Information Processing Systems, 2006.

[14] I. E. Givoni, C. Chung, and B. J. Frey, “Hierarchical affinity propagation,” Conference on Uncertainty in Artificial Intelligence, 2011.

[15] R. Duda, P. Hart, and D. Stork, Pattern Classification. Wiley-Interscience, October 2004.

[16] D. Dueck and B. J. Frey, “Non-metric affinity propagation for unsupervised image categorization,” International Conference in Computer Vision, 2007.

[17] N. Lazic, B. J. Frey, and P. Aarabi, “Solving the uncapacitated facility location problem using message passing algorithms,” International Conference on Artificial Intelligence and Statistics, 2007.

[18] R. Jenatton, J. Y. Audibert, and F. Bach, “Structured variable selection with sparsity-inducing norms,” Journal of Machine Learning Research, vol. 12, pp. 2777–2824, 2011.

[19] J. A. Tropp., “Algorithms for simultaneous sparse approximation. part ii: Convex relaxation,” Signal Processing, special issue “Sparse approximations in signal and image processing”, vol. 86, pp. 589–602, 2006.

[20] M. Aharon, M. Elad, and A. M. Bruckstein, “K-SVD: An algorithm for designing overcomplete dictionaries for sparse representation,” IEEE Trans. on Signal Processing, vol. 54, no. 11, pp. 4311–4322, 2006.

[21] J. J. Hull, “A database for handwritten text recognition research,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 16, no. 5, pp. 550–554, 1994.

[22] M. Fanty and R. Cole, “Spoken letter recognition,” in Neural Information Processing Systems, 1991. 9