IDEALS Home University of Illinois at Urbana-Champaign logo The Alma Mater The Main Quad

SRDA: An Efficient Algorithm for Large Scale Discriminant Analysis

Show full item record

Bookmark or cite this item: http://hdl.handle.net/2142/11336

Files in this item

File Description Format
PDF SRDA An Efficie ... Discriminant Analysis.pdf (249KB) (no description provided) PDF
Title: SRDA: An Efficient Algorithm for Large Scale Discriminant Analysis
Author(s): Cai, Deng; He, Xiaofei; Han, Jiawei
Subject(s): algorithms
Abstract: Linear Discriminant Analysis (LDA) has been a popular method for extracting features which preserve class separability. The projection functions of LDA are commonly obtained by maximizing the between class covariance and simultaneously minimizing the within class covariance. It has been widely used in many fields of information processing, such as machine learning, data mining, information retrieval, and pattern recognition. However, the computation of LDA involves dense matrices eigen-decomposition which can be computationally expensive both in time and memory. Specifically, LDA has O(mnt+t^3) time complexity and requires O(mn+mt+nt) memory, where m is the number of samples, n is the number of features and t=\min(m,n). When both m and n are large, it is infeasible to apply LDA. In this paper, we propose a novel algorithm for discriminant analysis, called {\em Spectral Regression Discriminant Analysis} (SRDA). By using spectral graph analysis, SRDA casts discriminant analysis into a regression framework which facilitates both efficient computation and the use of regularization techniques. Specifically, SRDA only needs to solve a set of regularized least squares problems and there is no eigenvector computation involved, which is a huge save of both time and memory. Our theoretical analysis shows that SRDA can be computed with O(ms) time and O(ms) memory, where s (\leq n) is the average number of non-zero features in each sample. Extensive experimental results on four real world data sets demonstrate the effectiveness and efficiency of our algorithm.
Issue Date: 2007-05
Genre: Technical Report
Type: Text
URI: http://hdl.handle.net/2142/11336
Other Identifier(s): UIUCDCS-R-2007-2857
Rights Information: You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the University of Illinois at Urbana-Champaign Computer Science Department under terms that include this permission. All other rights are reserved by the author(s).
Date Available in IDEALS: 2009-04-22
 

This item appears in the following Collection(s)

Show full item record

Item Statistics

  • Total Downloads: 403
  • Downloads this Month: 6
  • Downloads Today: 0

Browse

My Account

Information

Access Key