Whenever ranking data are collected, such as in elections, surveys, and database searches, it is frequently the case that partial rankings are available instead of, or sometimes in addition to, full rankings. Statistical methods for partial rankings have been discussed in the literature. However, there has been relatively little published on their Fourier analysis, perhaps because the abstract nature of the transforms involved impede insight. This paper provides as its novel contributions an analysis of the Fourier transform for partial rankings, with particular attention to the first three ranks, while emphasizing on basic signal processing properties of transform magnitude and phase. It shows that the transform and its magnitude satisfy a projection invariance and analyzes the reconstruction of data from either magnitude or phase alone. The analysis is motivated by appealing to corresponding properties of the familiar DFT and by application to two real-world data sets. 1. Introduction Ranking data, which arise in scenarios such as elections or database searches, describe how many times a given ordering of objects is chosen. It is frequently the case that when, ranking data are collected, partial ranking data are obtained in addition to, or perhaps instead of, full rankings. A partial or incomplete ranking only specifies the ordering of the top out of possibilities and usually indicates that the ranker is either unable to, or indifferent to, the ordering of the remaining items. Full ranking data are obviously a special case of partial ranking data. A classic approach is to treat full ranking data for items as a function on the symmetric group ; for each permutation , the value of is the number of times the ordering represented by that permutation is chosen [1]. For example, if 3 items are ranked, then is the number of times the survey respondents chose to rank item 2 first, item 1 second, followed by 3. As discussed in more detail below, partial ranking data also form functions on that are piecewise constant over cosets of the subgroup fixing the first items. The analysis of ranking data, including both full and partial rankings, is well established. Statistical methods exist both for data in the “time domain” (using signal processing terminology), which in this case is the permutation group , and in the “frequency domain” that is obtained through Fourier analysis on the group. Recent papers by Lebanon and Mao [2] and Hall and Miller [3] explore, respectively, the nonparametric modeling and bootstrap analysis of partial ranking data in the time domain.
References
[1]
P. Diaconis, “A generalization of spectral analysis with application to ranked data,” The Annals of Statistics, vol. 17, no. 3, pp. 949–979, 1989.
[2]
G. Lebanon and Y. Mao, “Non-parametric modeling of partially ranked data,” Journal of Machine Learning Research, vol. 9, pp. 2401–2429, 2008.
[3]
P. Hall and H. Miller, “Modeling the variability of rankings,” The Annals of Statistics, vol. 38, no. 5, pp. 2652–2677, 2010.
[4]
P. Diaconis, Group Representations in Probability and Statistics, Institute of Mathematical Statistics, Hayward, Calif, USA, 1988.
[5]
P. Diaconis and B. Sturmfels, “Algebraic algorithms for sampling from conditional distributions,” The Annals of Statistics, vol. 26, no. 1, pp. 363–397, 1998.
[6]
J. Huang, C. Guestrin, and L. Guibas, “Fourier theoretic probabilistic inference over permutations,” Journal of Machine Learning Research, vol. 10, pp. 997–1070, 2009.
[7]
R. Kondor and K. Borgwardt, “The skew spectrum of graphs,” in Proceedings of the International Conference on Machine Learning (ICML), A. McCallum and S. Roweis, Eds., pp. 496–503, Omnipress, 2008.
[8]
R. Kakarala, “A signal processing approach to Fourier analysis of ranking data: the importance of phase,” IEEE Transactions on Signal Processing, vol. 59, no. 4, pp. 1518–1527, 2011.
[9]
A. V. Oppenheim, A. S. Willsky, and S. H. Nawab, Sigals and Systems, Prentice-Hall, 2nd edition, 1996.
[10]
R. Kondor, “ ob: a C++ library for fast Fourier transforms on the symmetric group,” 2006, http://www.its.caltech.edu/~risi/index.html.
[11]
P. Lancaster and M. Tismenetsky, The Theory of Matrices, Computer Science and Applied Mathematics, Academic Press, Orlando, Fla, USA, 2nd edition, 1985.
[12]
E. Hewitt and K. A. Ross, Abstract Harmonic Analysis. Vol. II: Structure and Analysis for Compact Groups. Analysis on Locally Compact Abelian Groups, Springer, New York, NY, USA, 1970.
[13]
R. Kondor, “The skew spectrum of functions on finite groups and their homogeneous spaces,” Representation Theory. In press, http://arxiv.org/abs/0712.4259.
[14]
M. Croon, “Latent class models for the analysis of rankings,” in New Developments in Psychological Choice Modeling, G. D. Solte, H. Feger, and K. C. Klauer, Eds., pp. 99–121, North-Holland, 1989.
[15]
D. K. Maslen, “The efficient computation of Fourier transforms on the symmetric group,” Mathematics of Computation, vol. 67, no. 223, pp. 1121–1147, 1998.
[16]
M. Clausen and R. Kakarala, “Computing Fourier transforms and convolutions of -invariant signals on in time linear in n,” Applied Mathematics Letters, vol. 23, no. 2, pp. 183–187, 2010.
