2011 RankAggregationviaNuclearNormMi

• (Gleich & Lim, 2011) ⇒ David F. Gleich, and Lek-heng Lim. (2011). “Rank Aggregation via Nuclear Norm Minimization.” In: Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2011) Journal. ISBN:978-1-4503-0813-7 doi:10.1145/2020408.2020425

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%222011%22+Rank+Aggregation+via+Nuclear+Norm+Minimization
• http://dl.acm.org/citation.cfm?id=2020408.2020425&preflayout=flat#citedby

Quotes

Author Keywords

• Algorithms; nuclear norm; rank aggregation; singular value decomposition; skew symmetric; web-based services

Abstract

The process of rank aggregation is intimately intertwined with the structure of skew symmetric matrices. We apply recent advances in the theory and algorithms of matrix completion to skew-symmetric matrices. This combination of ideas produces a new method for ranking a set of items. The essence of our idea is that a rank aggregation describes a partially filled skew-symmetric matrix. We extend an algorithm for matrix completion to handle skew-symmetric data and use that to extract ranks for each item.

Our algorithm applies to both pairwise comparison and rating data. Because it is based on matrix completion, it is robust to both noise and incomplete data. We show a formal recovery result for the noiseless case and present a detailed study of the algorithm on synthetic data and Netflix ratings.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2011 RankAggregationviaNuclearNormMi	David F. Gleich Lek-heng Lim			Rank Aggregation via Nuclear Norm Minimization				10.1145/2020408.2020425		2011