• Networks, Graph Data and Robust Machine Learning

We have been developing machine learning tools for complex networks and graphs. These efforts include developing distributed optimization techniques to design the next generation of large-scale machine learning algorithms. Also as a fundamental problem in financial networks, we are working on the understanding of shock propagation and contagion in such networks. Our research mainly focuses on modeling the default propagation over complex financial networks using machine learning, and using such models for the detection and prevention of contagion at the very early stages.

Inspired by ideas in min-max games, we are also working on robust training of machine learning models. We are specifically interested in algorithms that come with performance guarantees. We use a broad class of optimization models for such problems, including convex and non-convex programming.

• Convex and Lossless Simplification of Deep Neural Networks with Performance Guarantee

Convex formulations for the training of neural networks and pruning their layered structure has been a rather open problem in the machine learning community. While adding sparsity promoting regularizers or heuristic thresholding techniques have been considered in various forms, mathematically provable frameworks to prune deep neural networks have remained unaddressed. Such analysis and model reduction are highly desirable tools for deep neural networks. While large networks are theoretically capable of learning arbitrarily complex models, overfitting and model redundancy negatively affects the prediction accuracy and model variance. In this context, we have developed Net-Trim, which is a layer-wise convex framework to prune (sparsify) deep neural networks.

The basic idea is to retrain the network layer by layer keeping the layer inputs and outputs close to the originally trained model, while seeking a sparse transform matrix. A main advantage of Net-Trim is breaking the curse of dimensionality by presenting a convex model, which is computationally distributable for big data. We mathematically show a consistency between the retrained model and the initially trained network. We also derive the general sufficient conditions for the recovery of a sparse transform matrix. In the case of standard Gaussian training samples of dimension n being fed to a layer, and s being the maximum number of nonzero terms across all columns of the transform matrix, we show that O(slog n) samples are enough to accurately learn a layer model. This type of analysis requires establishing concentration bounds for the sum of dependent random matrices. Net-Trim allows rebuilding much simpler networks, which are able to respond identically to the training data while reducing the error in the test case.

• Interpretable Machine Learning and Convex Cardinal Shape Composition

A main focus of our research in the past years has been on understandable machine learning models. These efforts include developing interpretable predictive models which obey nature's physical laws. Basically, the model training does not only happen through the data, and the models are designed in a way to be intrinsically consistent with a set of external rules. We have also been working on a general class of combinatorial problems with applications in computer vision, object learning, machine perception and operations research. These class of algorithms allow designing classification models which are extremely easy and intuitive to interpret by humans. The algorithms are mainly presented in the form of logical composition models. In characterizing objects within an image, often the geometry of interest can be viewed as a composition of simpler building blocks selected from of dictionary of prototype shapes. The composition here would exploit set operative interactions, simply because objects usually interact through such operators (overlapping modeled by the sets union and occlusion modeled by the set difference). For a more precise presentation of the problem, consider a variational objective, minimizing which characterizes objects of interest in the image (or classify data in higher dimensions). We are given a fixed collection of prototype shapes (or decision blocks) and a shape composition rule which allows combining shapes through multiple unions and a set exclusion. The combinatorial problem of interest is biasing the outcomes of the variational problem with the proposed composition rule, while regularizing the problem by restricting the number of contributing elements to a certain degree.

Addressing this problem is computationally intractable as the search domain grows exponentially with the number of allowed elements in the composition. For instance, a simplified and special case of this problem is the geometric packing problem, which is known to be NP-hard. In the context of computer vision, we have been able to develop a convex proxy to this problem, which efficiently addresses many instances of the problem in polynomial time. We have also been able to state sufficient conditions under which the convex proxy recovers a target composition and relate this solution to the outcome of the combinatorial problem. The conditions are expressed in terms of the lucidity of the object in the image and the geometric coherence between the object and the elements of the dictionary. Some interesting applications of the proposed problem in computer vision are: multi-resolution shape descriptors, finding principal shape components, solving challenging character recognition problems (as complex as CAPTCHA) and solving jigsaw and tiling puzzles.

• Fast Algorithms in Computational Optics

We develop computational algorithms with immediate applications in optics, ultra-fast imaging and 3D display designs. As a first example we discuss the problem of inspection and imaging through scattering layers. Although high-resolution time-of-flight measurement in time-domain spectroscopy provides 3D information, unfortunately it also induces an unwanted sensitivity to misalignments of the system and distortion of the layers themselves. We propose and implement an algorithmic framework based on low-rank matrix recovery and alternating minimization to remove such unwanted distortions from time-domain images. The method allows for recovery of the original sample texture in spite of the presence of temporal-spatial distortions.

Another work is creating immersive 3D stereoscopic, autostereoscopic, and lightfield experiences, which are becoming the center point of optical design of future head mounted displays and lightfield displays. Despite the advancement in 3D and light field displays, there is no consensus on what are the necessary quantized depth levels for such emerging displays at stereoscopic or monocular modalities. We propose a general optimization framework, which locates the depth levels in a globally optimal way for band limited displays. While the original problem is computationally intractable, we manage to find a tractable reformulation as maximally covering a region of interest with a selection of hypographs corresponding to the monocular depth of field profiles. The study provides fundamental guidelines for designing optimal near eye displays, light-field monitors, and 3D screens.

• Multi-Structured Recovery in Inverse Problems

Structured recovery has received a lot of attention in the recent years. In this context, the main objective is to incorporate prior structures (often combinatorial) into the reconstruction process to enhance the quality of the results with fewer measurements. The majority of results in this area correspond to the cases that only a single structure such as sparsity or low rank is taken into account.

An interesting avenue of research is taking additional structures into account to further reduce the number of measurements. In order to provide a mathematically established recovery scheme, the following steps need to be taken:

• Deriving sufficient conditions on the measurement system, which warrant the identifiability of a legitimate solution to the problem

• Providing a computationally tractable equivalence of the combinatorial problem via a convex formulation or other polynomial time algorithms

• Deriving conditions under which the solution to the tractable formulation coincides with the solution of the combinatorial problem

Our research in this area continues to develop computationally tractable schemes that overcome the aforementioned challenges and bring further efficiency into the problem by taking multiple structures into account.

• Sparse Shape Composition and Nonlinear Sparse Recovery

We propose a new mathematical and algorithmic framework for shape-based modeling with applications to various image processing and tomography problems. Applications vary from medical and geophysical tomography to object identification and characterization, optical character recognition, object tracking, and occluded shape recovery. The essential idea is to build up shapes in an image by geometric composition of a small number of (sparsely selected) prototype shapes in a dictionary. These prototypes may either be shapes with simple geometries or shape priors that are likely to be related to the structure of the target geometry (as shown in the figure).

This interesting problem bridges the gap between two active fields in the imaging society, namely the sparse recovery problem and the shape-based reconstruction. Despite the intuitive idea behind the sparse shape composition, the problem tends to be a hard combinatorial problem, which is not computationally tractable even for moderate size dictionaries. Formulating the problem concretely and incorporating it into a reconstruction process is an interesting open problem. In our publication “sparse shape reconstruction”, we have been able to relax the problem by defining so called knoll functions, which characterize shapes by their support. We have shown that for smooth functional associated with the shape-based problem, this relaxation can convert the problem into a nonlinear sparse recovery problem. An optimization algorithm is developed for this problem, which has shown to be a powerful asset to reach the desired goal.

• Multi-Modal Inverse Problems and Data Fusion

In recent years, there has been increasing interest in the development of inversion methods that process highly disparate data sets to obtain a unified reconstruction. A standard approach to joint inversion is composing a set of data fidelity functionals and finding a Pareto optimal point for the resulting multi-objective problem. Unfortunately, finding a Pareto point through a basic scalarization approach becomes an extremely hard problem when the physical modalities have discordant sensitivities. Another challenge is stably inverting for the unknown parameters when the dimensionality of the problem is dauntingly large. We have developed MOLMA, a multi-objective Levenberg-Marquardt algorithm that recovers the Pareto solution iteratively, warranting that after every iteration all functionals are sufficiently decreased. This approach helps skipping the early local Pareto points associated with a dominant cost and effectively extracts the joint characteristics from the combined data sets. Furthermore, to overcome the high dimensionality of the problem, a parametric level set representation permits extracting the geometric features of the inclusions without struggling with a high dimensional problem.

The proposed inversion toolbox is employed in an extraordinarily hard environmental problem where the ultimate goal is to determine the geometry of water contaminant source zones from some field measurements. The data considered are downstream concentration measurements away from the source zone and electromagnetic measurements in the periphery of the imaging domain (see the figure). Jointly inverting the multi-phase flow data along with electromagnetic data for a 3D domain with the least simplifying assumptions is an extremely challenging task that is successfully performed via the proposed technique.

• Parametric Level Set Method

In the context of inverse problems, level set (LS) method applies to shape-based inverse problems where the objective is the identification and characterization of regions of interest in a medium. Despite the topological flexibility and some level of dimensionality reduction, prevalent LS techniques rely on the pixel values. As a result, they require careful regularization and undergo intricate implementation details.

We have developed a technique, so called the parametric level set (PaLS) method, which significantly improves the quality of the reconstructions. This method is a mesh-less technique that relies on appropriately parameterizing the level set function and results in a significantly lower dimensional problem. PaLS enjoys the regularization by parameterization which intrinsically well-poses the problem. It also resolves the numerical concerns with traditional LS, such as re-initialization, use of a signed distance function and speed function extension. An interesting feature of the proposed technique is a pseudo-logical behavior and parametric narrow banding, which enables representing complex geometries by few parameters. For a detailed description of the method we refer you to the corresponding publication.