OEM Algorithm for Big Data

• Activity Number: 581
• Type: Invited
• Date/Time: Thursday, August 7, 2014 : 8:30 AM to 10:20 AM
• Sponsor: Section on Physical and Engineering Sciences
• Author(s): Peter Qian*+ and Shifeng Xiong and Bin Dai
• Companies: University of Wisconsin-Madison and Chinese Academy of Science and Tower Research Capital

Abstract

We propose a new algorithm, called OEM (a.k.a. orthogonalizing EM), intended for ordinary or regularized least squares problems with Big Data. The first step, named active orthogonization, orthogonalizes an arbitrary regression matrix by elaborately adding more rows. The second step imputes the responses corresponding to the new rows. The third step solves the chosen least squares problem for the complete orthogonal design. Because of the orthogonal structure of the complete data, both the second and third steps have close-form solutions and involve no matrix inversion. The algorithm has several attractive theoretical properties, such as achieving group coherence for fully aliased regression matrices and providing a local maximum for SCAP with the oracle property. In terms of numerical performance, OEM is very fast for problems with large sample size. The underlying idea of OEM also motivated the development of a new method, called iKriging (a.k.a. iterative Kriging), for fitting Big Data from computer experiments or spatial models.