jmlr jmlr2008 jmlr2008-81 jmlr2008-81-reference knowledge-graph by maker-knowledge-mining

81 jmlr-2008-Regularization on Graphs with Function-adapted Diffusion Processes


Source: pdf

Author: Arthur D. Szlam, Mauro Maggioni, Ronald R. Coifman

Abstract: Harmonic analysis and diffusion on discrete data has been shown to lead to state-of-the-art algorithms for machine learning tasks, especially in the context of semi-supervised and transductive learning. The success of these algorithms rests on the assumption that the function(s) to be studied (learned, interpolated, etc.) are smooth with respect to the geometry of the data. In this paper we present a method for modifying the given geometry so the function(s) to be studied are smoother with respect to the modified geometry, and thus more amenable to treatment using harmonic analysis methods. Among the many possible applications, we consider the problems of image denoising and transductive classification. In both settings, our approach improves on standard diffusion based methods. Keywords: diffusion processes, diffusion geometry, spectral graph theory, image denoising, transductive learning, semi-supervised learning


reference text

M. Belkin. Problems of learning on manifolds. PhD thesis, University of Chicago, 2003. M. Belkin and P. Niyogi. Using manifold structure for partially labelled classification. Advances in NIPS, 15, 2003a. M. Belkin and P. Niyogi. Laplacian eigenmaps and spectral techniques for embedding and clustering. In Advances in Neural Information Processing Systems 14 (NIPS 2001), pages 585–591. MIT Press, Cambridge, 2001. M. Belkin and P. Niyogi. Laplacian eigenmaps for dimensionality reduction and data representation. Neural Computation, 6(15):1373–1396, June 2003b. M. Belkin and P. Niyogi. Semi-supervised learning on Riemannian manifolds. Machine Learning, 56(Invited Special Issue on Clustering):209–239, 2004. TR-2001-30, Univ. Chicago, CS Dept., 2001. Mikhail Belkin and Partha Niyogi. Towards a theoretical foundation for laplacian-based manifold methods. In COLT, pages 486–500, 2005. P. B´ rard, G. Besson, and S. Gallot. Embedding Riemannian manifolds by their heat kernel. Geom. e and Fun. Anal., 4(4):374–398, 1994. T. Boult, R.A. Melter, F. Skorina, and I. Stojmenovic. G-neighbors. Proc. SPIE Conf. Vision Geom. II, pages 96–109, 1993. A. Buades, B. Coll, and J. M. Morel. A review of image denoising algorithms, with a new one. Multiscale Model. Simul., 4(2):490–530 (electronic), 2005a. ISSN 1540-3459. A. Buades, B. Coll, and J. M. Morel. Denoising image sequences does not require motion estimation. CMLA Preprint, (12), 2005b. 1735 S ZLAM , M AGGIONI AND C OIFMAN T. F. Chan and J. Shen. Image processing and analysis. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2005. ISBN 0-89871-589-X. Variational, PDE, wavelet, and stochastic methods. O. Chapelle, B. Sch¨ lkopf, and A. Zien, editors. Semi-Supervised Learning. MIT Press, Cambridge, o MA, 2006. URL http://www.kyb.tuebingen.mpg.de/ssl-book. R.T. Chin and C.L. Yeh. Quantitative evaluation of some edge-preserving noise-smoothing techniques. Computer Vision, Graphics, and Image Processing, 23:67–91, 1983. F. R. K. Chung. Spectral graph theory, volume 92 of CBMS Regional Conference Series in Mathematics. Published for the Conference Board of the Mathematical Sciences, Washington, DC, 1997. ISBN 0-8218-0315-8. R. R. Coifman and D. L. Donoho. Translation-invariant de-noising. Technical report, Department of Statistics, 1995. URL citeseer.ist.psu.edu/coifman95translationinvariant.html. R. R. Coifman, S. Lafon, A. B. Lee, M. Maggioni, B. Nadler, F. Warner, and S. W. Zucker. Geometric diffusions as a tool for harmonic analysis and structure definition of data: Diffusion maps. PNAS, 102(21):7426–7431, 2005a. doi: 10.1073/pnas.0500334102. URL http: //www.pnas.org/cgi/content/abstract/102/21/7426. R. R. Coifman, S. Lafon, A. B. Lee, M. Maggioni, B. Nadler, F. Warner, and S. W. Zucker. Geometric diffusions as a tool for harmonic analysis and structure definition of data: Diffusion maps. PNAS, 102(21):7432–7438, 2005b. doi: 10.1073/pnas.0500334102. R.R. Coifman and S. Lafon. Diffusion maps. Appl. Comp. Harm. Anal., 21(1):5–30, 2006a. R.R. Coifman and S. Lafon. Geometric harmonics: a novel tool for multiscale out-of-sample extension of empirical functions. Appl. Comp. Harm. Anal., 21(1):31–52, 2006b. R.R. Coifman and M. Maggioni. Multiscale data analysis with diffusion wavelets. Proc. SIAM Bioinf. Workshop, Minneapolis, April 2007. Tech. Rep. YALE/DCS/TR-1335, 2005. R.R. Coifman and M. Maggioni. Diffusion wavelets. Appl. Comp. Harm. Anal., 21(1):53–94, July 2006. (Tech. Rep. YALE/DCS/TR-1303, Yale Univ., Sep. 2004). M. Datar, N. Immorlica, P. Indyk, and V. S. Mirrokni. Locality-sensitive hashing scheme based on p-stable distributions. In SCG ’04: Proceedings of the twentieth annual symposium on Computational geometry, pages 253–262, New York, NY, USA, 2004. ACM Press. ISBN 1-58113-885-7. doi: http://doi.acm.org/10.1145/997817.997857. L.S. Davis and A. Rosenfeld. Noise cleaning by iterated local averaging. IEEE Tran. on Systems, Man, and Cybernetics, 8:705–710, 1978. D. L. Donoho and C. Grimes. When does isomap recover natural parameterization of families of articulated images? Technical Report Tech. Rep. 2002-27, Department of Statistics, Stanford University, August 2002. D. L Donoho and IM Johnstone. Ideal denoising in an orthonormal basis chosen from a library of bases. Technical report, Stanford University, 1994. 1736 R EGULARIZATION ON G RAPHS WITH F UNCTION - ADAPTED D IFFUSION P ROCESSES M. Elad. the origin of the bilateral filter and ways to improve it, 2002. URL citeseer.ist.psu. edu/elad02origin.html. R.E. Graham. Snow-removal - a noise-stripping process for picture signals. IRE Trans. on Inf. Th., 8:129–144, 1961. L. Greengard and V. Rokhlin. The rapid evaluation of potential fields in particle systems. MIT Press, 1988. Matthias Hein, Jean-Yves Audibert, and Ulrike von Luxburg. From graphs to manifolds - weak and strong pointwise consistency of graph laplacians. In COLT, pages 470–485, 2005. T.S. Huang, G.J. Yang, and G.Y. Tang. A fast two-dimensional median filtering algorithm. IEEE Trans. Acoustics, Speech, and Signal Processing, 27(1):13–18, 1979. P.W. Jones, M. Maggioni, and R. Schul. Manifold parametrizations by eigenfunctions of the Laplacian and heat kernels. Proc. Nat. Acad. Sci., 2007a. to appear. P.W. Jones, M. Maggioni, and R. Schul. Universal local manifold parametrizations via heat kernels and eigenfunctions of the Laplacian. submitted, 2007b. http://arxiv.org/abs/0709.1975. R. Kannan, S. Vempala, and A. Vetta. On clusterings: good, bad and spectral. J. ACM, 51(3): 497–515 (electronic), 2004. ISSN 0004-5411. J. Koenderink. The structure of images. Biological Cybernetics, 50:363–370, Jan 1984. R. I. Kondor and J. Lafferty. Diffusion kernels on graphs and other discrete structures. In Proceedings of the ICML, 2002. S. Lafon. Diffusion maps and geometric harmonics. PhD thesis, Yale University, Dept of Mathematics & Applied Mathematics, 2004. Stephane Lafon and Ann B. Lee. Diffusion maps and coarse-graining: A unified framework for dimensionality reduction, graph partitioning and data set parameterization. To appear in IEEE Pattern Analysis and Machine Intelligence, to appear, 2006. J.S. Lee. Digital image enhancement and noise filtering by use of local statistics. IEEE Trans. Pattern Anal. Mach. Intell., 2(2):165–168, 1980. T. Lindeberg. Scale-Space Theory in Computer Vision. Kluwer Academic Publishers, 1994. N. Linial, A. Samorodnitsky, and A. Wigderson. A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents. In STOC ’98: Proceedings of the thirtieth annual ACM symposium on Theory of computing, pages 644–652, New York, NY, USA, 1998. ACM Press. ISBN 0-89791-962-9. doi: http://doi.acm.org/10.1145/276698.276880. M. Maggioni and S. Mahadevan. Multiscale diffusion bases for policy iteration in markov decision processes. submitted, 2006. in preparation. M. Maggioni and S. Mahadevan. Fast direct policy evaluation using multiscale analysis of markov diffusion processes. In University of Massachusetts, Department of Computer Science Technical Report TR-2005-39; accepted at ICML 2006, 2005. 1737 S ZLAM , M AGGIONI AND C OIFMAN M. Maggioni and H. Mhaskar. Diffusion polynomial frames on metric measure spaces. ACHA, 2007. in press. M. Maggioni, J.C. Bremer Jr., R.R. Coifman, and A.D. Szlam. Biorthogonal diffusion wavelets for multiscale representations on manifolds and graphs. volume 5914, page 59141M. SPIE, 2005. URL http://link.aip.org/link/?PSI/5914/59141M/1. S. Mahadevan and M. Maggioni. Value function approximation with diffusion wavelets and laplacian eigenfunctions. In University of Massachusetts, Department of Computer Science Technical Report TR-2005-38; Proc. NIPS 2005, 2005. S. Mahadevan and M. Maggioni. Proto-value functions: A spectral framework for solving markov decision processes. JMLR, 8:2169–2231, 2007. S. Mahadevan, K. Ferguson, S. Osentoski, and M. Maggioni. Simultaneous learning of representation and control in continuous domains. In AAAI. AAAI Press, 2006. G. Mahmoudi, M.; Sapiro. Fast image and video denoising via nonlocal means of similar neighborhoods. IEEE Signal Processing Letters, 12(12):839–842, 2005. A. Ng, M. Jordan, and Y. Weiss. On spectral clustering: Analysis and an algorithm, 2001. URL citeseer.ist.psu.edu/ng01spectral.html. P. Perona and J. Malik. Scale-space and edge detection using anisotropic diffusion. IEEE Trans. Pattern Anal. Mach. Intell., 12(7):629–639, 1990. V.C. Raykar, C. Yang, R. Duraiswami, and N. Gumerov. Fast computation of sums of gaussians in high dimensions. Technical Report CS-TR-4767, Department of Computer Science, University of Maryland, CollegePark, 2005. L. I. Rudin, S. Osher, and E. Fatemi. Nonlinear total variation based noise removal algorithms. Phys. D, 60(1-4):259–268, 1992. ISSN 0167-2789. doi: http://dx.doi.org/10.1016/0167-2789(92) 90242-F. A. Shashua, R. Zass, and T. Hazan. Multiway clustering using supersymmetric nonnegative tensor factorization. Technical report, Hebrew University, Computer Science, Sep 2005. J. Shi and J. Malik. Normalized cuts and image segmentation. IEEE Tran PAMI, 22(8):888–905, 2000. A. Singer. From graph to manifold Laplacian: the convergence rate. Appl. Comp. Harm. Anal., 21 (1):128–134, July 2006. R. Sinkhorn. A relationship between arbitrary positive matrices and doubly stochastic matrices. Annals of Mathematical Statistics, 35(2):876–879, 1964. R. Sinkhorn and P. Knopp. Concerning nonnegative matrices and doubly stochastic matrices. Pacific Journal of Mathematics, 21(2):343–349, 1967. 1738 R EGULARIZATION ON G RAPHS WITH F UNCTION - ADAPTED D IFFUSION P ROCESSES S. M. Smith and J. M. Brady. SUSAN – A new approach to low level image processing. Technical Report TR95SMS1c, Chertsey, Surrey, UK, 1995. URL citeseer.ist.psu.edu/ smith95susan.html. A. Smola and R. Kondor. Kernels and regularization on graphs, 2003. URL citeseer.ist.psu. edu/smola03kernels.html. G. W. Soules. The rate of convergence of sinkhorn balancing. Linear Algebra and its Applications, 150(3):3–38, 1991. A.D. Szlam, M. Maggioni, R.R. Coifman, and J.C. Bremer Jr. Diffusion-driven multiscale analysis on manifolds and graphs: top-down and bottom-up constructions. volume 5914-1, page 59141D. SPIE, 2005. URL http://link.aip.org/link/?PSI/5914/59141D/1. M. Szummer and T. Jaakkola. Partially labeled classification with markov random walks. In Advances in Neural Information Processing Systems, volume 14, 2001. URL citeseer.ist.psu. edu/szummer02partially.html. http://www.ai.mit.edu/people/szummer/. C. Tomasi and R. Manduchi. Bilateral filtering for gray and color images. Proc. IEEE Inter. Conf. Comp. Vis., 1998. D. Tschumperle. PDE’s Based Regularization of Multivalued Images and Applications. PhD thesis, Universite de Nice-Sophia Antipolis, 2002. U. von Luxburg, M. Belkin, and O. Bousquet. Consistency of spectral clustering. Technical Report TR-134, Max Planck Insitute for Biological Cybernetics, 2004. M. Wakin, D. Donoho, H. Choi, and R. Baraniuk. The Multiscale Structure of Non-Differentiable Image Manifolds. In Optics & Photonics, San Diego, CA, July 2005. A. P. Witkin. Scale-space filtering. In Proc. 8th int. Joint Conf. Art. Intell., pages 1019–1022, 1983. Karlsruhe, Germany. L. P. Yaroslavsky. Digital Picture Processing. Springer-Verlag New York, Inc., Secaucus, NJ, USA, 1985. ISBN 0387119345. L. Yin, R. Yang, M. Gabbouj, and Y. Neuvo. Weighted median filters: a tutorial. IEEE Trans. on Circuits and Systems II: Analog and Digital Signal Processing, 43(3):155–192, 1996. R. Zass and A. Shashua. A unifying approach to hard and probabilistic clustering. In International Conference on Computer Vision (ICCV), Oct 2005. L. Zelnik-Manor and P. Perona. Self-tuning spectral clustering. Eighteenth Annual Conference on Neural Information Processing Systems, (NIPS), 2004. H. Zha, C. Ding, M. Gu, X. He, and H.D. Simon. Spectral relaxation for k-means clustering. In NIPS 2001, pages 1057–1064. MIT Press, Cambridge, 2001. D. Zhou and B. Schlkopf. Regularization on discrete spaces. pages 361–368, Berlin, Germany, 08 2005. Springer. X. Zhu, Z. Ghahramani, and J. Lafferty. Semi-supervised learning using gaussian fields and harmonic functions, 2003. URL citeseer.ist.psu.edu/zhu03semisupervised.html. 1739