Linear Discriminant Analysis with the Randomized Kaczmarz Method

Abstract

We present a randomized Kaczmarz method for linear discriminant analysis (rkLDA), an iterative randomized approach to binary-class Gaussian model linear discriminant analysis (LDA) for very large data. We harness a least squares formulation and mobilize the stochastic gradient descent framework to obtain a randomized classifier with performance that can achieve comparable accuracy to that of full data LDA. We present analysis for the expected change in the LDA discriminant function if one employs the randomized Kaczmarz solution in lieu of the full data least squares solution that accounts for both the Gaussian modeling assumptions on the data and algorithmic randomness. Our analysis shows how the expected change depends on quantities inherent in the data such as the scaled condition number and Frobenius norm of the input data, how well the linear model fits the data, and choices from the randomized algorithm. Our experiments demonstrate that rkLDA can offer a viable alternative to full data LDA on a range of step-sizes and numbers of iterations.

References in corpus (6)

• SciPy 1.0--Fundamental Algorithms for Scientific Computing in Python
• Sketching as a Tool for Numerical Linear Algebra
• Paved with Good Intentions: Analysis of a Randomized Block Kaczmarz Method
• Randomized Extended Kaczmarz for Solving Least-Squares
• Randomized Kaczmarz solver for noisy linear systems
• On the Randomized Kaczmarz Algorithm