final_report.toc

\contentsline {section}{\numberline {1}Introduction}{3}{section.1}%
\contentsline {subsection}{\numberline {1.1}Low rank Approximation}{3}{subsection.1.1}%
\contentsline {subsection}{\numberline {1.2}Kernel Methods}{3}{subsection.1.2}%
\contentsline {section}{\numberline {2}SVD}{4}{section.2}%
\contentsline {subsection}{\numberline {2.1}SVD}{4}{subsection.2.1}%
\contentsline {subsection}{\numberline {2.2}Best Rank-k Approximation}{4}{subsection.2.2}%
\contentsline {subsection}{\numberline {2.3}SVD Computation and Drawbacks}{5}{subsection.2.3}%
\contentsline {paragraph}{Power Method}{5}{section*.2}%
\contentsline {section}{\numberline {3}Nystr$\ddot {\rm o}$m Method}{6}{section.3}%
\contentsline {subsection}{\numberline {3.1}Nystr$\ddot {\rm o}$m Method\ in Low Rank Approximation}{6}{subsection.3.1}%
\contentsline {subsection}{\numberline {3.2}Error Bound}{7}{subsection.3.2}%
\contentsline {subsection}{\numberline {3.3}Drawbacks of Nystr$\ddot {\rm o}$m Method}{7}{subsection.3.3}%
\contentsline {section}{\numberline {4}BKA}{8}{section.4}%
\contentsline {subsection}{\numberline {4.1}Relation to K-Means Clustering}{8}{subsection.4.1}%
\contentsline {paragraph}{Shift-Invariant Kernel Matrix}{9}{section*.3}%
\contentsline {subsection}{\numberline {4.2}Low Rank Structure}{10}{subsection.4.2}%
\contentsline {section}{\numberline {5}MEKA}{13}{section.5}%
\contentsline {subsection}{\numberline {5.1}Steps of MEKA}{13}{subsection.5.1}%
\contentsline {paragraph}{Compute $W^{(s)}$}{14}{section*.4}%
\contentsline {paragraph}{Compute $L^{(s, t)}$}{14}{section*.5}%
\contentsline {paragraph}{Choose $k_s$ for Each Cluster}{15}{section*.6}%
\contentsline {subsection}{\numberline {5.2}Time Complexity and Storage Usage}{15}{subsection.5.2}%
\contentsline {section}{\numberline {6}Summary \& Discussion}{16}{section.6}%