Learning linear transformations
ALAN M. FRIEZE, Mark Jerrum, Ravi Kannan · 2002
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.