2014 Fall: Mathematical Introduction to Data Science

A Mathematical Introduction to Data Science (数据分析的数学导论)
Fall 2014

Course Information

Synopsis (摘要)

This course is open to graduates and senior undergraduates in applied mathematics and statistics who are interested in learning from data. Students with other backgrounds such as engineering and biology are also welcome, provided you have certain maturity of mathematics. It covers some topics on high dimensional statistics, manifold learning, diffusion geometry, random walks on graphs, concentration of measure, random matrix theory, geometric and topological methods, etc.
Prerequisite: linear algebra, basic probability and multivariate statistics, basic stochastic process (Markov chains); familarity with Matlab or R.

Lecture Notes (constantly updated)

[pdf download]

Time and Place:

Tuesday 6:40-9:30pm;
The 3rd Lecture Hall (三教) Rm 403
eBanshu classroom

Homework and Projects:

We are targeting weekly homeworks with monthly mini-projects, and a final major project. No final exam. Scribers will get bonus credit for their work!

Teaching Assistant (助教):

XIONG, Jiechao (熊杰超) Email: datascience_hw (add "AT 126 DOT com" afterwards)

Schedule (时间表)

Date	Topic	Instructor	Scriber
09/16/2013, Tue	Lecture 01: Introduction to Course Syllabus [pdf]	Yuan Yao
09/23/2013, Tue	Lecture 02: MDS and PCA [pdf] [Homework 1]: Homework 1 [pdf]. Deadline: 09/30/2014, Tuesday. Mark on the head of your homework: Name - Student ID.	Yuan Yao
09/30/2013, Tue	Lecture 03: Random Projections [pdf] [Reference]: A beautiful paper on phase transitions: Living on the Edge: Phase Transitions in Convex Programs with Random Data by Amelunxen, Lotz, Mccoy and Tropp [Homework 2]: Homework 2 [pdf]. Deadline: 10/14/2014, Tuesday. Mark on the head of your homework: Name - Student ID.	Yuan Yao
10/14/2013, Tue	Lecture 04: Stein's Phenomenon [pdf] [Reference]: Iain Johnstone's classic monograph: Gaussian Estimation free download! [Homework 3]: Homework 3 [pdf], Typo corrected!. Deadline: 10/21/2014, Tuesday. Mark on the head of your homework: Name - Student ID.	Yuan Yao
10/21/2012, Tue	Lecture 05: Manifold Learning (Nonlinear Dimensionality Reduction): ISOMAP vs. LLE [slides] [Reference]: [ISOMAP]: a science (2000) paper on MDS with geodesic distance (graph shortest path distance); [LLE]: a science (2000) paper on Locally Linear Embedding, i.e. local pca (complement) with global alignment; [Matlab]: isomap.m : isomap by Tennenbaum, de Silva isomapII.m : isomap by Tennenbaum, de Silva with sparsity, fast mex with dijkstra.cpp and fibheap.h lle.m : lle with k-nearest neighbors kcenter.m : k-center algorithm to find 'landmarks' in a metric space [Homework 4]: Homework 4 [pdf]. Deadline: 10/28/2014, Tuesday. Mark on the head of your homework: Name - Student ID.	Yuan Yao
10/28/2012, Tue	Lecture 06: Manifold Learning (Nonlinear Dimensionality Reduction): LLE extensions [slides] [Reference]: [Laplacian]: Laplacian Eigenmap (LLE) by Misha Belkin and Partha Niyogi 2003; [Hessian]: Hessian Eigenmap (LLE) by David Donoho and Carrie Grimes 2003; [LTSA]: Local Tangent Space Alignment by Hongyuan Zha and Zhenyue Zhang 2005; [Hein05]: consistency of Laplacian Eigenmap [Luxburg08]: consistency of Spectral Clustering [ZhaZha09]: consistency of LTSA [Matlab]: L2_distance.m : Pairwise L2_Distance between data points. hlle.m : Hessian LLE (eigenmap) matlab codes. mani.m : Todd Wittman's manifold learning demo (MDS, ISOMAP, LLE, Hessian LLE, Laplacian, Diffusion, LTSA) Todd Wittman's slides on comparison of manifold learning techniques	Yuan Yao
11/2/2012, Sun	Lecture 07: Random Matrix Theory for PCA [slides] [Reference]: [Johnstone06] shows that in high-dimensional inference when p/n is fixed, PCA will not converge by random matrix theory. [Nadakuditi10] gives a brief treatment on phase transitions appeared in PCA when p/n is fixed. [Terry Tao's talk slides on Random Matrix Theory with Universality] [Parallel Analysis: Horn (1965) original paper] [Parallel Analysis: Buja-Eyuboglu (1992) with random permutation]	Yuan Yao
11/4/2012, Tue	Lecture 08: SDP relaxations: Robust PCA and Sparse PCA [slides] [Reference]: [RPCA]: Robust Pricipal Component Analysis. [SPCA]: Sparse Pricipal Component Analysis formulated by a Semidefinite Programming. [Parrilo_SIAM09]: Robust PCA with a view of convex Algebraic Geometry. Emmanuel Candes talk at PKU, Oct 2011 [Matlab]: testRPCA.m : my matlab codes for RPCA, based on CVX. testSPCA.m : my matlab codes for SPCA, based on CVX. CVX : Matlab software for Disciplined Convex Programming, a basic package for semidefinite programming. Yi MA's webpage of Low-Rank Matrix Recovery at UIUC : many references and matlab codes [Project 1]: Homework 5 and Mini-Project 1 [pdf]. Deadline: 11/18/2014, Tuesday. Mark on the head of your homework: Name - Student ID.	Yuan Yao
11/18/2012, Tue	Lecture 09: Random Walks on Graphs I: Perron-Frobenius Theory and Primary Eigenvector [lecture notes] [Matlab]: pagerank.m : PageRank/HITS algorithms in matlab [Homework 6]: Homework 6 [pdf]. Deadline: 11/25/2014, Tuesday. Mark on the head of your homework: Name - Student ID.	Yuan Yao	Xiaowei Wang Zhimei Ren
11/25/2012, Tue	Lecture 10: Random Walks on Graphs II: Cheeger Inequalities and Second Eigenvector [lecture notes] [Homework 7]: Homework 7 [pdf]. Deadline: 12/2/2014, Tuesday. Mark on the head of your homework: Name - Student ID.	Yuan Yao	Shaokun LI
12/2/2012, Tue	Lecture 11: Random Walks on Graphs III: Lumpability vs. Multiple Spectral Clustering and Transition Path Theory vs. Semisupervised Learning [lecture notes] [Matlab]: DCSBM simulation : simulation of Degree-Corrected-Stochastic-Block-Models in matlab normalized Mutual Information : normalized mutual information in matlab [Homework 8]: Homework 7 [pdf]. Deadline: 12/7/2014, Tuesday. Mark on the head of your homework: Name - Student ID.	Yuan Yao	Zhimei Ren Xiaowei Wang Yongyi Guo
12/9/2012, Tue	Lecture 12: SDP Extension of MDS [lecture notes in ebanshu]	Yuan Yao
12/16/2012, Tue	Lecture 13: Compressed Sensing and High-Dimensional Statistics [lecture notes] [Homework 9]: Homework 9 [pdf]. Deadline: 12/30/2014, Tuesday. Mark on the head of your homework: Name - Student ID.	Yuan Yao	Xiaowei Wang Yongyi Guo Zhimei Ren
12/23/2012, Tue	Lecture 14: From Graphs to Complexes: Topological Data Analysis [slides] [lecture notes in Ebanshu]	Yuan Yao
12/30/2012, Tue	Lecture 15: Applied Hodge Theory in Data Analysis [slides] [lecture notes in Ebanshu] [Final Project]: Final project description [pdf]. Deadline: 1/20/2015, Tuesday. Please write to me if you would like to work on your own problems.	Yuan Yao

Reference

Books

[Boyd09] Boyd and Vandenbergh. Convex Optimization, 7th ed. (2009). [pdf]

[Chung97] Chung, Fan R.K. Spectral Graph Theory. 1997, AMS-CBMS. [Chapter 1-4]

[ChungLu06] Chung and Lu. Complex Graphs and Networks. 2006, AMS-CBMS. [Some chapters]

[ESL] Hastie, Tibshirani, and Friedman. The Elements of Statistical Learning. 2008, Springer. [Online book]

[GE] Iain Johnstone. Gaussian Estimation: Sequence and Wavelet Models. Draft June 11, 2013. [Online book]

[KemenySnell76] Kemeny and Snell. Finite Markov Chains. 1976.

[Kleinberg10] Easley and Kleinberg. Networks, Crowds, and Markets. 2010, Cambridge.

[Matrix] Golub and Van Loan. Matrix Computation. 1996.

[PageRank] Langville and Meyer. Google's PageRank and Beyond: The Science of Search Engine Rankings. 2006, Princeton University Press. [Google book]

[SHDD] Buhlmann and van de Geer. Statistics for High-Dimensional Data. 2011, Springer.

[Tao] Tao, Terrence. Topics in random matrix theory. Lecture Notes in UCLA. [pdf] [Online Book from Terry's BLOG]

[Tsybakov09] Tsybakov. Introduction to Nonparametric Estimation. 2009, Springer. [Online Book]

Papers

[Achlioptas01] Achlioptas, Dimitris (2001) "Database-friendly Random Projections". Proc 20th ACM Symp Principles of Database Systems, Santa Barbara, CA, 2001, 274-281. [pdf].

[Arun87] Arun, K. S., Huang, T. S., and Blostein, S. D. (1987) Least-squares fitting of two 3-D point sets. IEEE Transactions on Pattern Analysis and Machine Intelligence, 9 (5), pp. 698-700. [pdf].

[Bavaud10] Bavaud, Francois (2010) "On the Schoenberg Transformations in Data Analysis: Theory and Illustrations". [arXiv].

[Laplacian] Belkin, M. and P. Niyogi (2003) "Laplacian eigenmaps for dimensionality reduction and data representation.". Neural Computation 15:1373-1396. [pdf].

[Belkin_Niyogi_NIPS2002] Belkin, M. and P. Niyogi (2002) "Using Manifold Structure for Partially Labelled Classification". NIPS 2002 [pdf].

[Ye06] P. Biswas, T.-C. Liang, K.-C. Toh, T.-C. Wang, and Y. Ye (2006) "Semidefinite programming approaches for sensor network localization with noisy distance measurements". IEEE Transactions on Automation Science and Engineering, 3 (2006), pp. 360--371. [pdf].

[BrinPage98] Sergey Brin, Larry Page (1998) "The Anatomy of a Large-Scale Hypertextual Web Search Engine". Proceedings of the 7th international conference on World Wide Web (WWW). Brisbane, Australia. pp. 107-117. [pdf].

[RPCA] E. J. Candes, X. Li, Y. Ma, and J. Wright (2009) "Robust Principal Component Analysis?". Journal of ACM, 58(1), 1-37. [pdf].

[Parrilo_SIAM09] V. Chandrasekaran, S. Sanghavi, P.A. Parrilo, A. Willsky (2009) "Rank-Sparsity Incoherence for Matrix Decomposition". http://arxiv.org/pdf/0906.2220 . [pdf].

[Chang08] Chang, Kung Ching, Kelly Pearson, and Tan Zhang (2008) "Perron-Frobenius theorem for nonnegative tensors". Commun. Math. Sci. Volume 6, Number 2 (2008), 507-520. [pdf].

[Chung07] Chung, Fan R.K. (2007) "Four proofs for the Cheeger inequality and graph partition algorithms". ICCM 2007. [pdf].

[Coifman05] Coifman, Lafon, Lee, Maggioni, Nadler, Warner, and Zucker (2005) Geometric diffusions as a tool for harmonic analysis and structure definition of data: Diffusion maps I; Multiscale Methods II. PNAS [I.pdf][II.pdf].

[CoifmanLafon06] Coifman and Lafon (2006) Diffusion maps. Applied and Computational Harmonic Analysis. [pdf].

[Dasgupta99] Dasgupta and Gupta (1999) "An Elementary Proof of Johnson-Lindenstrauss Lemma" Technical Report, ICSI Berkeley. Extended version at Random Structures and Algorithms, 2003, 22(1):60-65. .

[SPCA_SDP] A. d'Aspremont, L. El Ghaoui, M. Jordan, and G. Lanckriet (2006) "A Direct Formulation of Sparse PCA using Semidefinite Programming". preprint arxiv.org/pdf/cs/0406021. Published at SIAM Review, vol. 49, no. 3, 2007. .

[Hessian] Donoho, D.L. and C. Grimes (2003) "Hessian Eigenmaps: New Locally Linear Embedding techniques for high dimensional data" PNAS 100 (10):5591-5596. .

[EfronMorris74] Efron, Bradley and Carl Morris (1974). Data Analysis using Stein's Estimator and Its Generalizations. [pdf]

[FanHoffman55] Fan, K. and Hoffman, A. J. (1987) Some Metric Inequalities in the Space of Matrices. Proceedings of the American Mathematical Society, 6 (1), pp. 111-116. [pdf].

[Fouss07-CommuteDistance] Fouss, Francois, Alain Pirotte, Jean-michel Renders, and Marco Saerens (2007) Random-walk computation of similarities between nodes of a graph, with application to collaborative recommendation. IEEE Transactions on Knowledge and Data Engineering, 19(3), pp. 355-369. [pdf].

[GobelJagers74] Gobel, F. and A. Jagers (1974). "Random Walks on Graphs". Stochastic Processes and Their Applications, 2: 311-336. [pdf].

[Hein05] Hein, M., J. Audibert, and U. von Luxburg (2005) From graphs to manifolds: weak and strong pointwise consistency of graph Laplacians, COLT, 2005. [pdf].

[Hochbaum10] Hochbaum, Dorit (2010) "Polynomial Time Algorithms for Ratio Regions and a Variant of Normalized Cut". IEEE Trans. Pattern Analysis and Machine Intelligence, 32, 2010. [pdf].

[Hunter06] Hunter, J.J. (2006) "Variances of first passage times in a Markov chain with applications to mixing times". Res. Lett. Inf. Math. Sci., 10:17-48, 2010. [pdf].

[Indyk98] Indyk, P. and R. Motwani (1998) "Approximate nearest neighbors: Towards removing the curse of dimensionality". Proc 30th Annu ACM Symp Theory of Computing, Dallas, TX, 1998, pp. 604-613. [pdf].

[Johnstone06] Johnstone, I (2006) High Dimensional Statistical Inference and Random Matrices. arXiv:0611589.

[Jones11] Peter Wilcox Jones, Andrei Osipov, and Vladimir Rokhlin (2011) Randomized Approximate Nearest Neighbhors Algorithm. PNAS, 2011 [pdf].

[Keller75] Keller, J. B. (1975) Closest Unitary, Orthogonal and Hermitian Operators to a Given Operator. Mathematics Magazine, 48 (4), pp. 192-197. [pdf].

[Kleinberg99] Kleinberg, Jon (1999). "Authoritative sources in a hyperlinked environment". Journal of the ACM 46 (5): 604-632. [pdf].

[KleinRandic93] Klein, D.J. and M. Randic (1993). "Resistance Distance". J. Math. Chemistry 12: 81-95. [pdf].

[Li2008] Li J.Z., et al. (2008). "Worldwide Human Relationships Inferred from Genome-Wide Patterns of Variation". Science 319(5866):1100-1104, 2008 .

[Luxburg07] Ulrike von Luxburg (2007). A tutorial on spectral clustering. [pdf]

[Luxburg08] Ulrike von Luxburg, Mikhail Belkin, and Olivier Bousquet (2008). Consistency of Spectral Clustering. Ann. Stat. 36(2): 555-586. [pdf]

[MeilaShi01] Meila and Shi (2001). "A random walk view of spectral segmentation". AISTAT'01 [pdf, 7.7 MB].

[Nadler_Srebro_NIPS2009] Nalder, Boaz, Nathan Srebro, and Xueyuan Zhou (2009) "Semi-Supervised Learning with the Graph Laplacian: The Limit of Infinite Unlabelled Data". NIPS 2009 [pdf].

[Nadakuditi10] Nadakuditi, R. R. and F. Benaych-Georges (2010) The breakdown point of signal subspace estimation. IEEE Sensor Array and Multichannel Signal Processing Workshop (October 2010), pg. 177-180 [pdf].

[QiuHancock07] Qiu, Huaijun, and E.R. Hancock (2007) "Clustering and Embedding Using Commute Times", IEEE Trans. Pattern Analysis and Machine Intelligence, 29(11): 1873-1890. [pdf].

[RadLuxHei09] Radl, Agnes, Ulrike von Luxburg, and Matthias Hein (2007) The Resistance Distance is Meaningless for Large Random Geometric Graphs. Workshop on Analyzing Networks and Learning with Graphs NIPS 2009 [pdf].

[LLE] Roweis, Sam T. and Saul K. Lawrence (2000) Locally Linear Embedding. Science, 290:2323-2326. [LLE Website].

[ShiMalik00] Shi, Jianbo and Jitendra Malik (2000). "Normalized Cuts and Image Segmentation". IEEE Transactions on Pattern Analysis and Machine Intelligence,22(8): 888-905. [pdf].

[Singer06] Singer, Amit (2006) From graph to manifold Laplacian: The convergence rate. Applied and Computational Harmonic Analysis. [pdf].

[Stein56] Stein, Charles (1956). Inadmissibility of the usual estimator for the mean of a multivariate distribution. 1974. Proceedings of the Third Berkeley Symposium on Mathematical Statistics and Probability. 1. pp. 197-206. [pdf]

[ISOMAP] Tenenbaum, J.B., V. de Silva and J. C. Langford (2000). A Global Geometric Framework for Nonlinear Dimensionality Reduction. Science, 290:2319-2323. [ISOMAP Website]

[MVU] Weinberger, Killian Q. and Lawrence K. Saul (2006). "Unsupervised Learning of Image Manifolds by Semidefinite Programming". International Journal of Computer Vision 70(1), 77-90, 2006 [pdf]

[ZhaZha09] Hongyuan Zha and Zhenyue Zhang (2009). "Spectral properties of the alignment matrices in manifold learning". SIAM Review. [pdf]

[LTSA] Zhenyue Zhang and Hongyuan Zha (2005). "Principal Manifolds and Nonlinear Dimension Reduction via Local Tangent Space Alignment". SIAM Journal of Scientific Computing 26(1)[pdf]

[ZhuLaf_ICML2003] Xiaojin Zhu, Zoubin Ghahramani and John Lafferty (2003). "Semi-Supervised Learning Using Gaussian Fields and Harmonic Functions". ICML 2003 [pdf]

Datasets

[Anzhen Heart Data] Heart Operation Effect Prediction, provided by Dr. Jinwen Wang, Anzhen Hospital

[DSP-Bidding Competition Data] Contest Website , provided by Dr. Xuehua Shen, iPinyou Co. Ltd.

[Keywords Pricing] Keywords and profit index in paid search advertising, by Hansheng Wang (Guanghua, PKU). [sample file] [readme.txt] [data in csv]

[Protein Folding] Protein Folding prediction from sequence variations, by Steve Smale and Massimo Andreatta (CityUHK). [compressed .zip] [readme.txt]

[红楼梦人物事件矩阵] a 376-by-475 matrix (374-by-475 updated by WAN, Mengting) for character-event appearance in A Dream of Red Mansion (Xueqin Cao) [374 Characters.txt (for R/read.table)] [HongLouMeng374.csv] [HongLouMeng376.xls] [.mat] [readme.m]

[Data_Gonewind] Gone with Wind Interaction Network in matlab, by Xiuyuan Cheng, 'A: 68-by-68 adjacency matrix; name: 68 character names'

[西游记] characters-scene occurance matrices for 100 chapters [data in matlab (302-by-408 matrix)]

chap001-005	chap006-009	chap010-013	chap014-017	chap018-021	chap022-025
chap026-029	chap030-033	chap034-037	chap038-041	chap042-045	chap046-049
chap050-053	chap054-057	chap058-061	chap062-065	chap066-069	chap070-073
chap074-077	chap078-081	chap082-085	chap086-088	chap089-091	chap092-094
chap095-097	chap098-100	All in TXT	readData.m