Collaborative Research: Sparse Optimization in Large Scale Data Processing: A Multiscale Proximity Approach

Old Dominion University Research Foundation, Norfolk VA

Investigators

Abstract

There is an emergent demand in areas of national strategic interest such as information technology, nanotechnology, biotechnology, civil infrastructure and environment for abstracting useful knowledge for decision making or uncovering truth from large-scale data acquired via various means such as sensors and internet. A core issue of these areas is to develop accurate mathematical models, which govern the abstraction process, and to design efficient algorithms that solve the underlying optimization problems for the models. A challenge of the tasks comes from the large-scale nature of given data. This nature requires determining a large number of model parameters and it is computationally expensive. To address this challenge, this project will take advantage of certain intrinsic multiscale structure of given data in modeling so that the resulting models have significantly fewer parameters to be determined. It is also crucial to introduce efficient algorithms for solving the resulting optimization problems for the models, which have intrinsic multiscale structures. The second goal of this proposed research is to provide rigorous training of young mathematicians and computational scientists so that they have the skill sets needed to face the challenges of the big data era through this proposed research and its associated educational components. Outcomes of the proposed research and its educational component will certainly contribute to the Federal strategic interest areas. This research project addresses several critical issues of processing large-scale data, such as high dimensionality and high noise, through properly choosing structured sparsity promoting non-convex functions in modeling and through synthesizing the multiscale representation of data and using fixed-point equations/inclusions involved the proximity operator in solving the resulting optimization problem. Structured non-convex sparsity promoting functions are proposed to overcome drawbacks of the existing modeling of large-scale data, leading to the design of efficient single-scale proximity algorithms. Multiscale analysis has been developed to efficiently represent data, while how multiscale representation of data is used to improve convergence of the fixed-point proximity algorithm remains unsolved. The proposed multiscale proximity method avoids iterations on the full large-scale of the fixed-point equation/inclusion. Instead, when data are represented in a multiscale analysis, iterations of the multiscale proximity algorithm are conducted only on a (small-scale) lower frequency component of the equation/inclusion (based on a single-scale algorithm), and only one functional evaluation on a (large-scale) high frequency component is required. The multiscale algorithm will preserve accuracy of the single-scale algorithm while accelerating its convergence significantly. This leads to a fast algorithm for solving the fixed-point equation/inclusion involved the proximity operator. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.