Learning Linear Transformations

We present a polynomial time algorithm to learn (in Valiant's PAC model) an arbitrarily oriented cube in n-space, given uniformly distributed sample points from it. In fact, we solve the more general problem of learning, in polynomial time, a linear (affine) transformation of a product distribution.

Authors

• Alan M. Frieze
• Mark Jerrum
• Ravindran Kannan

Keywords

• Polynomials
• Computer science
• Mathematics
• Random variables
• Probability distribution
• Linear algebra
• Independent component analysis
• Collaboration
• Gaussian distribution
• Computer networks
• Linear Transformation
• Product Distribution
• Polynomial-time Algorithm
• Normal Distribution
• Local Maxima
• Variance-covariance Matrix
• Second Moment
• Correction Algorithm
• Matrix M
• Nonsingular
• Isometry
• Unknown Vector
• Proof Of The Lemma
• Identically Zero
• Fourth Moment
• Standard Basis Vector