STATISTICAL METHODS WITH APPLICATIONS TO
                 MACHINELEARNINGANDARTIFICIAL
                           INTELLIGENCE
                               AThesis
                              Presented to
                           The Academic Faculty
                                by
                              Yibiao Lu
                           In Partial Fulfillment
                        of the Requirements for the Degree
                          Doctor of Philosophy in the
                H. Milton Stewart School of Industrial and Systems Engineering
                         Georgia Institute of Technology
                              August 2012
                              c
                         Copyright 
 2012 by Yibiao Lu
                       STATISTICAL METHODS WITH APPLICATIONS TO
                              MACHINELEARNINGANDARTIFICIAL
                                                INTELLIGENCE
                    Approved by:
                    Professor Xiaoming Huo, Advisor          Professor Alex Shapiro
                    H. Milton Stewart School of Industrial   H. Milton Stewart School of Industrial
                    and Systems Engineering                  and Systems Engineering
                    Georgia Institute of Technology          Georgia Institute of Technology
                    Professor Shi-Jie Deng                   Professor Panagiotis Tsiotras
                    H. Milton Stewart School of Industrial   The Daniel Guggenheim School of
                    and Systems Engineering                  Aerospace Engineering
                    Georgia Institute of Technology          Georgia Institute of Technology
                    Professor Ming Yuan                      Date Approved: Apr 26, 2012
                    H. Milton Stewart School of Industrial
                    and Systems Engineering
                    Georgia Institute of Technology
                                                  TABLEOFCONTENTS
                       LIST OF TABLES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .             vi
                       LIST OF FIGURES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .             vii
                       SUMMARY. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .          xii
                       I    THEORETICALRESULTSONHIGH-ORDERLAPLACIAN-BASED
                            REGULARIZATION IN FUNCTION ESTIMATION . . . . . . .                                  1
                            1.1   Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .     1
                            1.2   Methodology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .      3
                                  1.2.1   Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . .    3
                                  1.2.2   Problem Formulation . . . . . . . . . . . . . . . . . . . . . .        5
                                  1.2.3   Choice of the Penalty Parameter λ . . . . . . . . . . . . . . .        6
                            1.3   Theoretical Properties . . . . . . . . . . . . . . . . . . . . . . . . . .     6
                                  1.3.1   Mathematical Preparation . . . . . . . . . . . . . . . . . . .         7
                                  1.3.2   Bounds of regularization matrix M’s eigenvalues . . . . . . .         11
                                  1.3.3   Convergence Rate of Multivariate GLS Estimator          . . . . . .   13
                                  1.3.4   Asymptotic Optimality of GCV . . . . . . . . . . . . . . . .          13
                            1.4   Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .    16
                            1.5   Appendix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .    17
                                  1.5.1   Detailed Proofs    . . . . . . . . . . . . . . . . . . . . . . . . .  17
                                  1.5.2   Agmon’s Theorem . . . . . . . . . . . . . . . . . . . . . . . .       36
                                  1.5.3   Neumann Boundary Condition . . . . . . . . . . . . . . . . .          37
                       II    BEAMLET-BASED GRAPH STRUCTURE FOR PATH PLAN-
                            NINGUSINGMULTISCALEINFORMATION . . . . . . . . . .                                 38
                            2.1   Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .    38
                            2.2   Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . .       41
                            2.3   Multiscale Path Planning Strategy with Preprocessed Information .             43
                                  2.3.1   Recursive Dyadic Partitioning of the Environment . . . . . .          44
                                  2.3.2   Beamlet-like Connectivity . . . . . . . . . . . . . . . . . . . .     46
                                                                    iii
                                   2.3.3   Bottom-Up Fusion Algorithm . . . . . . . . . . . . . . . . . .           50
                                   2.3.4   Multiscale A* Algorithm on the Beamlet Graph . . . . . . .               52
                             2.4   Complexity Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . .        53
                                   2.4.1   Complexity of Information Fusion Part . . . . . . . . . . . .            53
                                   2.4.2   Complexity of Searching       . . . . . . . . . . . . . . . . . . . .    57
                                   2.4.3   Memory Usage . . . . . . . . . . . . . . . . . . . . . . . . . .         59
                                   2.4.4   Preprocessing Time . . . . . . . . . . . . . . . . . . . . . . .         60
                             2.5   Numerical Studies . . . . . . . . . . . . . . . . . . . . . . . . . . . .        61
                                   2.5.1   Comparison Based on L1 Heuristic . . . . . . . . . . . . . . .           61
                                   2.5.2   Comparison Using Stronger Heuristics . . . . . . . . . . . . .           64
                             2.6   Discussion and Related Prior Work         . . . . . . . . . . . . . . . . . .    65
                                   2.6.1   Beamlets as a Predecessor       . . . . . . . . . . . . . . . . . . .    65
                                   2.6.2   Related Work . . . . . . . . . . . . . . . . . . . . . . . . . .         66
                             2.7   Conclusions     . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .    71
                        III AN INCREMENTAL, MULTI-SCALE SEARCH ALGORITHM
                             FORDYNAMICPATHPLANNINGWITHLOWWORST-CASE
                             COMPLEXITY . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .               73
                             3.1   Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .       73
                             3.2   Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . .          77
                             3.3   The Multiscale A* and Lifelong Planning A* Algorithms              . . . . . .   79
                                   3.3.1   The Multiscale A* (m-A*) Algorithm . . . . . . . . . . . . .             79
                                   3.3.2   Incremental Search Algorithm: LPA* . . . . . . . . . . . . .             82
                             3.4   Multiscale Strategy in Dynamic Path Planning: m-LPA*               . . . . . .   84
                                   3.4.1   Dynamic Path-Finding Reduced Recursive Dyadic Partition .                84
                                   3.4.2   Update of Multiscale Information in the Beamlet Graph . . .              85
                                   3.4.3   LPA* Algorithm on the Beamlet Graph . . . . . . . . . . . .              87
                             3.5   Complexity Analysis and Data Structure . . . . . . . . . . . . . . .             90
                                   3.5.1   Worst-Case Complexity Analysis . . . . . . . . . . . . . . . .           90
                                   3.5.2   Fibonacci vs Binomial Heap Implementation . . . . . . . . .              91
                                                                      iv