Compressive classification: where wireless communications meets machine learning. (English) Zbl 1332.94011
Boche, Holger (ed.) et al., Compressed sensing and its applications. MATHEON workshop, Berlin, Germany, December 2013. Cham: Birkhäuser/Springer (ISBN 978-3-319-16041-2/hbk; 978-3-319-16042-9/ebook). Applied and Numerical Harmonic Analysis, 451-468 (2015).
Summary: This chapter introduces Shannon-inspired performance limits associated with the classification of low-dimensional subspaces embedded in a high-dimensional ambient space from compressive and noisy measurements. In particular, it introduces the diversity-discrimination tradeoff that describes the interplay between the number of classes that can be separated by a compressive classifier – measured via the discrimination gain – and the performance of such a classifier – measured via the diversity gain – and the relation of such an interplay to the underlying problem geometry, including the ambient space dimension, the subspaces dimension, and the number of compressive measurements. Such a fundamental limit on performance is derived from a syntactic equivalence between the compressive classification problem and certain wireless communications problems. This equivalence provides an opportunity to cross-pollinate ideas between the wireless information theory domain and the compressive classification domain. This chapter also demonstrates how theory aligns with practice in a concrete application: face recognition from a set of noisy compressive measurements.
For the entire collection see [Zbl 1320.94007].
For the entire collection see [Zbl 1320.94007].
References:
| [1] | Adini, Y.; Moses, Y.; Ullman, S., Face recognition: the problem of compensating for changes in illumination direction, IEEE Trans. Pattern Anal. Mach. Intell., 19, 7, 721-732 (1997) · doi:10.1109/34.598229 |
| [2] | Aggarwal, V., Ashikhmin, A., Calderbank, R.: A Grassmannian packing based on the Nordstrom-Robinson code. In: IEEE Information Theory Workshop, Chengdu, China, pp. 1-5 (2006) |
| [3] | Alon, U.; Barkai, N.; Notterman, D. A.; Gish, K.; Ybarra, S.; Mack, D.; Levine, A. J., Broad patterns of gene expression revealed by clustering analysis of tumor and normal colon tissues probed by oligonucleotide arrays, Proc. Natl. Acad. Sci., 96, 12, 6745-6750 (1999) · doi:10.1073/pnas.96.12.6745 |
| [4] | Ashikhmin, A., Calderbank, R.: Space-time Reed-Muller codes for noncoherent MIMO transmission. In: IEEE International Symposium on Information Theory, Adelaide, Australia, 1952-1956 (2005) |
| [5] | Ashikhmin, A., Calderbank, R., Kewlin, W.: Multidimensional second order Reed-Muller codes as Grassmannian packings. In: IEEE International Symposium on Information Theory, Seattle, WA, USA, pp. 1001-1005 (2006) |
| [6] | Ashikhmin, A.; Calderbank, R., Grassmannian packings from operator Reed-Muller codes, IEEE Trans. Inf. Theory, 56, 10, 5689-5714 (2010) · Zbl 1366.94574 · doi:10.1109/TIT.2010.2070192 |
| [7] | Basri, R.; Jacobs, D. W., Lambertian reflectance and linear subspaces, IEEE Trans. Pattern Anal. Mach. Intell., 25, 2, 218-233 (2003) · doi:10.1109/TPAMI.2003.1177153 |
| [8] | Calderbank, R.; Hardin, R. H.; Rains, E. M.; Shor, P. W.; Sloane, N. J.A., A group-theoretic framework for the construction of packings in Grassmannian spaces, J. Algebraic Comb., 9, 129-140 (1999) · Zbl 0941.51033 · doi:10.1023/A:1018673825179 |
| [9] | Candès, E.; Romberg, J.; Tao, T., Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information, IEEE Trans. Inf. Theory, 52, 2, 489-509 (2006) · Zbl 1231.94017 · doi:10.1109/TIT.2005.862083 |
| [10] | Candès, E.; Romberg, J.; Tao, T., Stable signal recovery from incomplete and inaccurate measurements, Commun. Pure Appl. Math., 59, 8, 1207-1223 (2006) · Zbl 1098.94009 · doi:10.1002/cpa.20124 |
| [11] | Candès, E.; Tao, T., Near-optimal signal recovery from random projections: universal encoding strategies?, IEEE Trans. Inf. Theory, 52, 12, 5406-5425 (2006) · Zbl 1309.94033 · doi:10.1109/TIT.2006.885507 |
| [12] | Carson, W. R.; Chen, M.; Rodrigues, M. R.D.; Calderbank, R.; Carin, L., Communications-inspired projection design with application to compressive sensing, SIAM J. Imaging Sci., 5, 4, 1185-1212 (2012) · Zbl 1260.94010 · doi:10.1137/120878380 |
| [13] | Chen, M.; Silva, J.; Paisley, J.; Wang, C.; Dunson, D.; Carin, L., Compressive sensing on manifolds using a nonparametric mixture of factor analyzers: algorithm and performance bounds, IEEE Trans. Signal Process., 58, 12, 6140-6155 (2010) · Zbl 0166.23301 · doi:10.1109/TSP.2010.2070796 |
| [14] | Chen, M., Carson, W.R., Rodrigues, M.R.D., Calderbank, R., Carin, L.: Communication-inspired linear discriminant analysis. In: International Conference on Machine Learning, Edinburgh, UK, pp. 919-926 (2012) |
| [15] | Davenport, M.; Boufounos, P.; Wakin, M.; Baraniuk, R., Signal processing with compressive measurements, IEEE J. Sel. Top. Sign. Process., 4, 2, 445-460 (2010) · doi:10.1109/JSTSP.2009.2039178 |
| [16] | Donoho, D., Compressed sensing, IEEE Trans. Inf. Theory, 52, 4, 1289-1306 (2006) · Zbl 1288.94016 · doi:10.1109/TIT.2006.871582 |
| [17] | Duda, R.O., Hart, P.E., Stork, D.G.: Pattern Classification, 2nd edn. Wiley-Interscience, New York, NY (2000) · Zbl 0968.68140 |
| [18] | Elhamifar, Vidal, R.: Sparse subspace clustering: algorithm, theory, and applications. IEEE Trans. Pattern Anal. Mach. Intell. 35(11), 2765-2781 (2013) |
| [19] | Georghiades, A. S.; Belhumeur, P. N.; Kriegman, D. J., From few to many: Illumination cone models for face recognition under variable lighting and pose, IEEE Trans. Pattern Anal. Mach. Intell., 23, 6, 643-660 (2001) · doi:10.1109/34.927464 |
| [20] | Hastie, T.; Simard, P. Y., Metrics and models for handwritten character recognition, Stat. Sci., 13, 1, 54-65 (1998) · Zbl 0966.68186 · doi:10.1214/ss/1028905973 |
| [21] | Hild, K.; Erdogmus, D.; Torkkola, K.; Principe, J., Feature extraction using information-theoretic learning, IEEE Trans. Pattern Anal. Mach. Intell., 28, 9, 1385-1392 (2006) · doi:10.1109/TPAMI.2006.186 |
| [22] | Hochwald, B. M.; Marzetta, T. L., Unitary space-time modulation for multiple-antenna communications in Rayleigh flat fading, IEEE Trans. Inf. Theory, 46, 2, 543-564 (2000) · Zbl 0999.94511 · doi:10.1109/18.825818 |
| [23] | Hochwald, B. M.; Marzetta, T. L.; Richardson, T. J.; Sweldens, W.; Urbanke, R., Systematic design of unitary spce-time constellations, IEEE Trans. Inf. Theory, 46, 6, 1962-1973 (2000) · Zbl 1004.94517 · doi:10.1109/18.868472 |
| [24] | Hull, J. J., A database for handwritten text recognition research, IEEE Trans. Pattern Anal. Mach. Intell., 16, 5, 550-554 (1994) · doi:10.1109/34.291440 |
| [25] | Kaski, S., Peltonen, J.: Informative discriminant analysis. In: International Conference on Machine Learning, Washington, DC, USA, pp. 329-336 (2003) |
| [26] | LeCun, Y., Jackel, L., Bottou, L., Brunot, A., Cortes, C., Denker, J., Drucker, H., Guyon, I., Muller, U., Sackinger, E., Simard, P., Vapnik, V.: Comparison of learning algorithms for handwritten digit recognition. In: International Conference on Artificial Neural Networks, Warsaw, Poland, pp. 53-60 (1995) |
| [27] | Lee, K.-C.; Ho, J.; Kriegman, D. J., Acquiring linear subspaces for face recognition under variable lighting, IEEE Trans. Pattern Anal. Mach. Intell., 27, 5, 684-698 (2005) · doi:10.1109/TPAMI.2005.92 |
| [28] | Liu, G., Lin, Z., Yu, Y.: Robust subspace segmentation by low-rank representation. In: International Conference on Machine Learning, Haifa, Israel, pp. 663-670 (2010) |
| [29] | Liu, L.; Fieguth, P., Texture classification from random features, IEEE Trans. Pattern Anal. Mach. Intell., 34, 3, 574-586 (2012) · doi:10.1109/TPAMI.2011.145 |
| [30] | Marzetta, T. L.; Hochwald, B. M., Capacity of a mobile multiple-antenna communication link in Rayleigh flat fading, IEEE Trans. Inf. Theory, 45, 1, 139-157 (1999) · Zbl 0946.94002 · doi:10.1109/18.746779 |
| [31] | Nenadic, Z., Information discriminant analysis: feature extraction with an information-theoretic objective, IEEE Trans. Pattern Anal. Mach. Intell., 29, 8, 1394-1407 (2007) · doi:10.1109/TPAMI.2007.1156 |
| [32] | Nokleby, M., Rodrigues, M.R.D., Calderbank, R.: Discrimination on the Grassmann manifold: fundamental limits of subspace classifiers. Available at http://arxiv.org/abs/1404.5187 · Zbl 1359.94146 |
| [33] | Qiu, Q., Sapiro, G.: Learning robust subspace clustering. Available at http://arxiv.org/abs/1308.0273 · Zbl 1337.68230 |
| [34] | Qiu, Q., Sapiro, G.: Learning transformations for clustering and classification. Available at http://arxiv.org/abs/1309.2074 · Zbl 1337.68230 |
| [35] | Qiu, Q., Sapiro, G.: Learning transformations for classification forests. Available at http://arxiv.org/abs/1312.5604 · Zbl 1337.68230 |
| [36] | Reboredo, H., Renna, F., Calderbank, R., Rodrigues, M.R.D.: Compressive classification of a mixture of Gaussians: analysis, designs and geometrical interpretation. Available at http://arxiv.org/abs/1401.6962 · Zbl 1414.94508 |
| [37] | Reeves, G.; Gastpar, M., The sampling rate distortion tradeoff for sparsity pattern recovery in compressed sensing, IEEE Trans. Inf. Theory, 58, 5, 3065-3092 (2012) · Zbl 1365.94184 · doi:10.1109/TIT.2012.2184848 |
| [38] | Reeves, G.; Gastpar, M., Approximate sparsity pattern recovery: information-theoretic lower bounds, IEEE Trans. Inf. Theory, 59, 6, 3451-3465 (2013) · Zbl 1364.94250 · doi:10.1109/TIT.2013.2253852 |
| [39] | Renna, F.; Calderbank, R.; Carin, L.; Rodrigues, M. R.D., Reconstruction of signals drawn from a Gaussian mixture from noisy compressive measurements, IEEE Trans. Signal Process., 62, 9, 2265-2277 (2014) · Zbl 1394.94482 · doi:10.1109/TSP.2014.2309560 |
| [40] | Ross, D. T., Systematic variation in gene expression patterns in human cancer cell lines, Nat. Genet., 24, 3, 227-235 (2000) · doi:10.1038/73432 |
| [41] | Royston, J. P., Some techniques for assessing multivariate normality based on the Shapiro-Wilk W, Appl. Stat., 32, 2, 121-133 (1983) · Zbl 0536.62043 · doi:10.2307/2347291 |
| [42] | Soltanolkotabi, M.; Candès, E., A geometric analysis of subspace clustering with outliers, Ann. Stat., 40, 4, 2195-2238 (2012) · Zbl 1318.62217 · doi:10.1214/12-AOS1034 |
| [43] | Soltanolkotabi, M., Elhamifar, E., Candès, E.: Robust subspace clustering. Available at arxiv.org/abs/1301.2603 · Zbl 1360.62353 |
| [44] | Tao, D.; Li, X.; Wu, X.; Maybank, S., Geometric mean for subspace selection, IEEE Trans. Pattern Anal. Mach. Intell., 31, 2, 260-274 (2009) · doi:10.1109/TPAMI.2008.70 |
| [45] | Torkkola, K.: Learning discriminative feature transforms to low dimensions in low dimensions. In: Advances in Neural Information Processing Systems, Vancouver, Canada, pp. 969-976 (2001) |
| [46] | Torkkola, K., Feature extraction by non-parametric mutual information maximization, J. Mach. Learn. Res., 3, 1415-1438 (2003) · Zbl 1044.81530 |
| [47] | Tenenbaum, J.; de Silva, V.; Langford, J., A global geometric framework for nonlinear dimensionality reduction, Science, 290, 5500, 2319-2323 (2000) · doi:10.1126/science.290.5500.2319 |
| [48] | Tulino, A.; Caire, G.; Verdú, S.; Shamai, S., Support recovery with sparsely sampled free random matrices, IEEE Trans. Inf. Theory, 59, 7, 4243-4271 (2013) · doi:10.1109/TIT.2013.2250578 |
| [49] | Wainwright, M., Sharp thresholds for high-dimensional and noisy sparsity recovery using l1-constrained quadratic programming (lasso), IEEE Trans. Inf. Theory, 55, 5, 2183-2202 (2009) · Zbl 1367.62220 · doi:10.1109/TIT.2009.2016018 |
| [50] | Wainwright, M., Information-theoretic limits on sparsity recovery in the high dimensional and noisy setting, IEEE Trans. Inf. Theory, 55, 12, 5728-5741 (2009) · Zbl 1367.94106 · doi:10.1109/TIT.2009.2032816 |
| [51] | Wang, W.; Wainwright, M.; Ramchandran, K., Information-theoretic limits on sparse signal recovery: Dense versus sparse measurement matrices, IEEE Trans. Inf. Theory, 56, 6, 2967-2979 (2010) · Zbl 1366.94130 · doi:10.1109/TIT.2010.2046199 |
| [52] | Wang, L., Carlson, D., Rodrigues, M.R.D., Wilcox, D., Calderbank, R., Carin, L.: Designed measurements for vector count data. In: Advances in Neural Information Processing Systems, Lake Tahoe, NV, USA, pp. 1142-1150 (2013) |
| [53] | Wang, L., Razi, A., Rodrigues, M.R.D., Calderbank, R., Carin, L.: Nonlinear information-theoretic compressive measurement design. In: International Conference on Machine Learning, Beijing, China, pp. 1161-1169 (2014) |
| [54] | Wang, Y., Xu, H.: Noisy sparse subspace clustering. In: International Conference on Machine Learning, Atlanta, GA, USA, pp. 89-97 (2013) |
| [55] | Wright, J.; Yang, M.; Ganesh, A.; Sastry, S.; Ma, Y., Robust face recognition via sparse representation, IEEE Trans. Pattern Anal. Mach. Intell., 31, 2, 210-227 (2009) · doi:10.1109/TPAMI.2008.79 |
| [56] | Zheng, L., Tse, D.: The diversity-multiplexing tradeoff for non-coherent multiple antenna channels. In: The Annual Allerton Conference on Communication, Control and Computing, Monticello, IL, USA, pp. 1011-1020 (2002) |
| [57] | Zheng, L.; Tse, D., Communication on the Grassmann manifold: a geometric approach to the noncoherent multiple-antenna channel, IEEE Trans. Inf. Theory, 48, 2, 359-383 (2002) · Zbl 0539.60048 · doi:10.1109/18.978730 |
| [58] | Zheng, L.; Tse, D., Diversity and multiplexing: a fundamental tradeoff in multiple-antenna channels, IEEE Trans. Inf. Theory, 49, 5, 1073-1096 (2003) · Zbl 1063.94531 · doi:10.1109/TIT.2003.810646 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
