2010 AScalableTwoStageApproachforaCl

• (Sun et al., 2010) ⇒ Liang Sun, Betul Ceran, and Jieping Ye. (2010). “A Scalable Two-stage Approach for a Class of Dimensionality Reduction Techniques.” In: Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2010). doi:10.1145/1835804.1835846

Subject Headings:

Notes

• Categories and Subject Descriptors: H.2.8 Database Management: Database Applications - Data Mining.
• General Terms: Algorithm

Cited By

• http://scholar.google.com/scholar?q=%22A+scalable+two-stage+approach+for+a+class+of+dimensionality+reduction+techniques%22+2010
• http://portal.acm.org/citation.cfm?id=1835846&preflayout=flat#citedby

Quotes

Author Keywords

Dimensionality reduction, generalized eigenvalue problem, least square, regularization, scalability

Abstract

Dimensionality reduction plays an important role in many data mining applications involving high-dimensional data. Many existing dimensionality reduction techniques can be formulated as a generalized eigenvalue problem, which does not scale to large-size problems. Prior work transforms the generalized eigenvalue problem into an equivalent least squares formulation, which can then be solved efficiently. However, the equivalence relationship only holds under certain assumptions without regularization, which severely limits their applicability in practice. In this paper, an efficient two-stage approach is proposed to solve a class of dimensionality reduction techniques, including Canonical Correlation Analysis, Orthonormal Partial Least Squares, linear Discriminant Analysis, and Hypergraph Spectral Learning. The proposed two-stage approach scales linearly in terms of both the sample size and data dimensionality. The main contributions of this paper include (1) we rigorously establish the equivalence relationship between the proposed two-stage approach and the original formulation without any assumption; and (2) we show that the equivalence relationship still holds in the regularization setting. We have conducted extensive experiments using both synthetic and real-world data sets. Our experimental results confirm the equivalence relationship established in this paper. Results also demonstrate the scalability of proposed two-stage approach.

References

,

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2010 AScalableTwoStageApproachforaCl	Jieping Ye Liang Sun Betul Ceran			A Scalable Two-stage Approach for a Class of Dimensionality Reduction Techniques		KDD-2010 Proceedings		10.1145/1835804.1835846		2010