The objective of this research is to establish new theory and efficient algorithms for identifying the major component(s) of statistically distributed data clouds in n-dimensional Euclidean space. Principal Component Analysis (PCA) is a method widely used for identifying the spread of data in mutually orthogonal directions. Conventional PCA is based on the l2 norm and Gaussian statistics and has excellent performance as long as there are no or extremely few outliers in the data. However, data clouds obtained under any conditions other than benign laboratory conditions often contain significant numbers of outliers (i.e., the error is mostly from a heavy-tailed distribution) which strongly limits the accuracy of PCA. To remedy this situation, ����������������robust PCAs��������������� that involve the l1 norm have been proposed over the past few years. In most of the l1 reformulations of PCA that have been proposed, l2-based steps (inner products, averages, singular values) and Gaussian-based concepts (averages, variances and covariances) are retained and use of the l1 norm is limited. A 2D/3D l1-based Major Component Detection and Analysis (l1 MCDA) method that does not use any of the conventional l2 or Gaussian steps or concepts has recently been developed and tested by the PI and his research group. The computational experiments support the superiority of l1 MCDA in detecting and analyzing the major components embedded in statistically distributed data clouds. It has recently been shown that a nonlinear 1-norm constrained optimization problem can be converted into a linear optimization problem over an l1-norm based first-order cone, but, the resulting problem may become intractable (NP-hard) in theory. The proposed research will uncover new theory and solution/approximation methods of linear conic programming to develop l1 MCDA for higher-dimensional data clouds that has ����������������all operations in l1��������������� and direct connection with heavy-tailed statistics. This research will create a robust tool in terrain and geometric modeling, audio/speech/image processing, face/object recognition, information mining and general pattern recognition. It is expected that l1 MCDA will be particularly useful for pattern recognition under patterned clutter. This capability will provide a basis for robust semantic labeling.

L1 splines, a new class of shape-preserving univariate and bivariate splines based on minimizing a functional involving the L1 norm rather than a conventional functional involving the square of the L2 norm, have over the past 12 years been shown to have superior shape-preserving behavior. The proposed research will create shape preservation results and algorithms for locally calculated univariate L1 approximating splines based on recent advances for locally calculated univariate L1 interpolating splines. The univariate L1 approximating splines on which we will focus will be L1 spline fits rather than L1 smoothing splines because L1 smoothing splines involve an unknown balance parameter á (for which no theoretical guidance is available) while L1 spline fits do not use such a parameter. Until 2011, L1 spline fits were less computationally efficient than L1 smoothing splines because, in the interior-point methods used at that time, L1 spline fits resulted in larger and less well conditioned matrices than did L1 smoothing splines. The new local approach that has been developed for L1 interpolating splines and the efficient analysis-based algorithm used to implement this approach has changed this situation and has raised the possibility that L1 spline fits will be computationally more advantageous than L1 smoothing splines. The specific topics of this research will be: new algorithms (iterative algorithms close to some preliminary algorithms already developed and noniterative bilevel optimization algorithms, including possible adaption of the Bloomfield-Steiger algorithm), analysis of shape preservation capabilities of L1 spline fits, computational experiments and, time and scope of effort permitting, linkage of analysis of L1 spline fits with statistical analysis of heavy-tailed distributions. The objective here is to shift from the global structure previously used for L1 approximating splines to the local structure that has been so successful for L1 interpolating splines. Larger effects of this univariate research will be: 1) It will lead to computationally cheap, shape-preserving nonparametric and parametric bi- and multivariate L1 spline fits for modeling irregular, multiscale 3D point clouds for reconstruction and texturing of urban terrain and of irregular geometrical objects. 2) It may lead to a new class of bilevel optimization algorithms.

The development of shape-preserving modeling techniques for interpolating and approximating multiscale data, that is, data with sudden large changes in magnitude or spacing, is a major objective in geometric modeling. Recently, a new class of splines, namely, L1 splines, that have superior shape-preserving behavior arose. These L1 splines have hitherto been calculated using global spline minimization principles. Recently, results have been published that suggest that the shape-preservation performance and the computational efficiency of L1 splines can be enhanced by replacing global spline minimization principles by spline minimization principles based on local windows. This is the opportunity that this proposal wishes to pursue. Specifically, we propose to create a new class of L1 splines that have superior geometric shape preservation (even better than before), do not require discretization of the spline functional and are computationally cheap (because they are locally calculated). We will first develop the theory and algorithms for univariate and bivariate interpolating splines and for univariate approximating splines and, on the basis of these results, develop the theory and algorithms for bivariate approximating splines. Our main goal is to further improve bivariate L1 approximating splines as a tool for parametric modeling in reconstruction and texturing of 3D urban terrain.

NCSU through the GIT Student will provide research and analysis to SAS as set forth in this Agreement. Such research and analysis shall include, but is not limited to, research, generation, testing, and documentation of operations research software. GIT Student will provide such services for SAS? offices in Cary, North Carolina, at such times as have been mutually agreed upon by the parties. GIT Student agrees to abide by SAS? policies and procedures regarding security of SAS? facilities and computing resources. GIT Student further agrees to submit to background verification. If SAS, in its sole discretion, finds GIT Student?s background unsuitable, this Agreement shall terminate immediately.

This proposal requests a total of $648,503 funding from National Science Foundation to support research project for January 1, 2006 ? December 31, 2008. The goal of this research is to give impetus to the exploration of deformable object modeling with force-torque feedback devices. The results of this research will provide necessary techniques for the development of new force-feedback haptic devices that support more accurate, adaptive and agile human-computer interaction for the next generation design and modeling. Dr. Lee (IE) will serve as the PI and Dr. Shu-Cherng Fang (IE) will serve as the Co-PI of this project.

In collaboration with UNC, NCSU team will produce an optimizer for use in conjunction with the Boeing Deeplook Logistics Simulation Environment to provide analysis on optimal investment options. The major effort is to Create an optimizer in conjunction with the Boeing Logistics and Support Modeling, Simulation, and Analysis Team. The Optimizer will be used in conjunction with a selected Boeing Deeplook simulation. The simulation will provide the optimizer?s key performance metrics and optimization parameters The simulation will be used to help senior leaders determine the optimal investment strategy for a given platform or program.

NCSU through the GIT Student will provide research and analysis to SAS as set forth in this Agreement. Such research and analysis shall include, but is not limited to, research, generation, testing, and documentation of operations research software. GIT Student will provide such services for SAS' offices in Car, North Carolina, at such times as have been mutually agreed upon by the parties. GIT Student agrees to abide by SAS' policies and procedures regarding security of SAS' facilities and computing resources. GIT Student further agrees to submit to background verification. If SAS, in its sole discretion, finds GIT Student's background unsuitable, this Agreement shall terminate immediately.

NCSU through the Research Assistant will provide reseearch and analysis to SAS Institute, Inc Cary, NC as set forth in this Agreement. Starting June 5, 2006, one graduate research assistant will be appointed as an industrial trainee and work closely with Trevor Kearney, Analytical Solutions Manager at SAS, until August 22, 2006. Such research and analysis shall include, but is not limited to, research, generation, testing, and documentation of operations research software. Professor Shu-Cherng Fang will serve as faculty advisor on this project.

WORK STATEMENT FOR ACCELERATION OF PROJECT 46943-MA-SR THEORY AND ALGORITHMS FOR L1 SPLINES In previous work on ARO grant 46943-MA-SR and a preceding grant, the theoretical (geometric programming) framework for L1 splines was established and computational results for univariate and bivariate L1 splines were generated in various settings (Cartesian, polar and spherical coordinates, second and first derivatives, Sibson and reduced Hsieh-Clough-Tocher elements). In all of these settings, L1 splines turned out to have superior shape preservation capabilities. However, L1 splines, which result in linear/nonlinear programs, are also quite expensive. The work that we propose here for acceleration of project 46943-MA-SR is focused on overcoming the computational complexity issues of L1 splines. The first step of overcoming these issues has already been completed by the development of a prototype compressed primal-dual method outlined under the first topic below. Based on the success with this prototype compressed primal-dual method, we propose to develop and test this method further, to implement it in a domain-decomposition framework that will further reduce the computing time and to transfer it from second-derivative-based L1 splines (in the current version) to first-derivative-based L1 splines. We will also develop of trivariate tetrahedral Worsey-Farin elements for implementation of L1 splines in 3D.

This is an incremental to a project in cooperation with SAS Institute Inc., Cary, NC. Starting from May 16, 2005, one graduate research assistant will be appointed as an industrial trainee and work closely with Trevor Kearney, Analytical Solutions Manager at SAS, until August 17, 2005. The trainee will search the litereature for research that has been done in areas where SAS is currently active or considering research projects; finalize documentation that has been started; document work that has been completed in the past; and do research and development as directed.