Spectral analysis of data

By Yossi Azar, Amos Fiat, Anna R. Karlin, Frank McSherry, Jared Saia. Symposium on the Theory of Computing, 2001

317 citations recorded by the source corpus.

Subfields: Computational Theory and Mathematics, Information Systems, Signal Processing

View Paper: https://www.semanticscholar.org/paper/620cf63f101f20c03a2e530c287c2603839de15e

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Information Systems

In Signal Processing

Citations in the corpus

Weighted low rank approximations with provable guarantees (2016, background): “Low rank approximation is arguably one of the most wellstudied problems in randomized numerical linear algebra, with diverse applications to clustering [19, 23, 38, 18], data mining [5], distance matrix completion [13], information retrieval [45], learning mixtures of distributions [2, 32], recommen”
A decentralized algorithm for spectral analysis (2004, background): “In addition, several recent results have also shown how to use spectral techniques for clustering [13, 18, 17], characterization [8, 15, 1], and recommendation/prediction [2].”
Collaborative recommendation: A robustness analysis (2004, background): “3.4 Related Work There has been substantial theoretical analysis and algorithmic work on collaborative recommendation [Kumar et al. 1998; Pennock et al. 2000; Azar et al. 2001; Drineas et al. 2002].”
Learning from Incomplete Ratings Using Non-negative Matrix Factorization (2006, background): “Generally, they can be divided into two categories: memory based algorithms [1, 6, 16, 17] and model based algorithms [2, 3, 5, 7, 11, 15, 18, 19, 20].”
Learning Topic Models -- Going beyond SVD (2012, background): “the topic vectors) [4], [22], [21], which suffices for some applications such as computing the inner product of two document vectors (in the space spanned by the topics) as a measure of their similarity.”
Generalization Error Bounds for Collaborative Prediction with Low-Rank Matrices (2004, background): “Or, other loss functions, such as squared error [3, 2], or zero-one loss versus the signs of entries in X, can be minimized.”
Sampling from large matrices: An approach through geometric functional analysis (2005, background): “rank approximation is feasible. The crucial assumption that A is essentially a low rank matrix holds in many applications. For example, this is a model hypothesis in the Latent Semantic Indexing (see [6, 21, 4, 9, 5, 2]). There A is the “document-term matrix”, which is formed of the frequencies of o”
Matrix estimation by Universal Singular Value Thresholding (2012, methodology): “ved widespread attention ever since the proliferation of large data sets. Early work using spectral analysis was done by a number of authors in the engineering literature, for example, by Azar et al. [10] and Achlioptas and McSherry [1]. This was followed by a sizable body of work on spectral method”
On the Nyström Method for Approximating a Gram Matrix for Improved Kernel-Based Learning (2005, background): “Related work taking advantage of low-rank structure includes [34, 20, 39, 8, 30, 38, 3].”
Graph spectral image smoothing using the heat kernel (2008, background): “However, the Laplacian spectrum is a rich source of information and also lends itself to a diverse set of problems including routing analysis [37] and information retrieval [38].”
Clustering Large Graphs via the Singular Value Decomposition (2004, methodology): “As an example, our algorithm could be used to perform Latent Semantic Indexing (LSI) (Berry & Linoff, 1997; Papadimitriou et al., 2000; Azar et al., 2001); this is a general technique for analyzing a collection of documents which are assumed to be related (for example, they are all documents…”
Improved Approximation Algorithms for Large Matrices via Random Projections (2006, background): “Our motivation comes from the widespread use of these tools in data mining [10].”
Exact Matrix Completion via Convex Optimization (2008, methodology): “This scenario was considered in [ 3 ] where it was shown that most of the entries can be reconstructed to o(1) error by computing the singular value decomposition of the matrix which is equal to Mij when (i, j ) ∈ � and zeros everywhere else.”
Weighted Low-Rank Approximations (2003, methodology): “The matrix was extended to the remaining jokes by projecting each joke column onto the column subspace of this matrix. rescaling Following Azar et al. (2001), the ratings for each joke were scaled inversely proportional to the frequency with which the joke was rated (between 0.197 and 0.77).”
Quantum Recommendation Systems (2016, unknown): “Email: aprakash@ntu.edu.sg.”
Link analysis ranking: algorithms, theory, and experiments (2005, methodology): “The notion of stability has been independently considered (but not explicitly de.ned) in a number of different papers [Ng et al. 2001a, 2001b; Azar et al. 2001; Achlioptas et al. 2001].”
Fast maximum margin matrix factorization for collaborative prediction (2005, methodology): “A common approach to collaborative prediction is to fit a factor model to the data, and use it in order to make further predictions (Azar et al., 2001; Billsus & Pazzani, 1998; Hofmann, 2004; Marlin & Zemel, 2004; Canny, 2004).”
Low-Rank Approximation and Regression in Input Sparsity Time (2012, background): “These problems have many applications in data mining [Azar et al. 2001], recommendation systems [Drineas et al. 2002], information retrieval [Papadimitriou et al. 2000], web search [Achlioptas et al. 2001; Kleinberg 1999], clustering [Drineas et al. 2004; McSherry 2001], and learning mixtures of…”