We study a matrix recovery problem with unknown correspondence: given the observation matrix $M_o=[A,\tilde P B]$, where $\tilde P$ is an unknown permutation matrix, we aim to recover the underlying matrix $M=[A,B]$. Such problem commonly arises in many applications where heterogeneous data are utilized and the correspondence among them are unknown, e.g., due to data mishandling or privacy concern. We show that, in some applications, it is possible to recover $M$ via solving a nuclear norm minimization problem. Moreover, under a proper low-rank condition on $M$, we derive a non-asymptotic error bound for the recovery of $M$. We propose an algorithm, $\text{M}^3\text{O}$ (Matrix recovery via Min-Max Optimization) which recasts this combinatorial problem as a continuous minimax optimization problem and solves it by proximal gradient with a Max-Oracle. $\text{M}^3\text{O}$ can also be applied to a more general scenario where we have missing entries in $M_o$ and multiple groups of data with distinct unknown correspondence. Experiments on simulated data, the MovieLens 100K dataset and Yale B database show that $\text{M}^3\text{O}$ achieves state-of-the-art performance over several baselines and can recover the ground-truth correspondence with high accuracy.

We propose a general learning based framework for solving nonsmooth and nonconvex image reconstruction problems. We model the regularization function as the composition of the $l_{2,1}$ norm and a smooth but nonconvex feature mapping parametrized as a deep convolutional neural network. We develop a descent-type algorithm to solve the nonsmooth nonconvex minimization problem by leveraging Nesterov's smoothing technique and the idea of residual learning, and learn the network parameters such that the outputs of the algorithm match the references in training data. Our method is versatile as one can employ various modern network structures into the regularization, and the resulting network inherits the convergence properties of the algorithm. We also show that the proposed network is parameter-efficient, and its performance compares favorably to the state-of-the-art methods in a variety of image reconstruction problems in practice.

We propose a novel learning framework based on neural mean-field dynamics for inference and estimation problems of diffusion on networks. Our new framework is derived from the Mori-Zwanzig formalism to obtain an exact evolution of the node infection probabilities, which renders a delay differential equation with memory integral approximated by learnable time convolution operators, resulting in a highly structured and interpretable RNN. Directly using cascade data, our framework can jointly learn the structure of the diffusion network and the evolution of infection probabilities, which are cornerstone to important downstream applications such as influence maximization. Connections between parameter learning and optimal control are also established. Empirical study shows that our approach is versatile and robust to variations of the underlying diffusion network models, and significantly outperform existing approaches in accuracy and efficiency on both synthetic and real-world data.

We propose a unified data-driven framework based on inverse optimal transport that can learn adaptive, nonlinear interaction cost function from noisy and incomplete empirical matching matrix and predict new matching in various matching contexts. We emphasize that the discrete optimal transport plays the role of a variational principle which gives rise to an optimization based framework for modeling the observed empirical matching data. Our formulation leads to a non-convex optimization problem which can be solved efficiently by an alternating optimization method. A key novel aspect of our formulation is the incorporation of marginal relaxation via regularized Wasserstein distance, significantly improving the robustness of the method in the face of noisy or missing empirical matching data. Our model falls into the category of prescriptive models, which not only predict potential future matching, but is also able to explain what leads to empirical matching and quantifies the impact of changes in matching factors. The proposed approach has wide applicability including predicting matching in online dating, labor market, college application and crowdsourcing. We back up our claims with numerical experiments on both synthetic data and real world data sets.

We propose a new two-stage joint image reconstruction method by recovering edges directly from observed data and then assembling an image using the recovered edges. More specifically, we reformulate joint image reconstruction with vectorial total-variation regularization as an $l_1$ minimization problem of the Jacobian of the underlying multimodality or multicontrast images. We provide detailed derivation of data fidelity for the Jacobian in Radon and Fourier transform domains. The new minimization problem yields an optimal convergence rate higher than that of existing primal-dual based reconstruction algorithms, and the per-iteration cost remains low by using closed-form matrix-valued shrinkages. We conducted numerical tests on a number of multicontrast CT and MR image datasets, which demonstrate that the proposed method significantly improves reconstruction efficiency and accuracy compared to the state-of-the-art joint image reconstruction methods.

User behaviors in social networks are microscopic with fine grained temporal information. Predicting a macroscopic quantity based on users’ collective behaviors is an important problem. However, existing works are mainly problem-specific models for the microscopic behaviors and typically design approximation or heuristic algorithms to compute the macroscopic quantity. In this paper, we propose a unifying framework with a jump stochastic differential equation model that systematically links the microscopic event data and macroscopic inference, and the theory to approximate its probability distribution. We showed that our method can better predict the user behaviors in real-world applications.

We propose the first multistage intervention framework that tackles fake news in social networks by combining reinforcement learning with a point process network activity model. The spread of fake news and mitigation events within the network is modeled by a multivariate Hawkes process with additional exogenous control terms. By choosing a feature representation of states, defining mitigation actions and constructing reward functions to measure the effectiveness of mitigation activities, we map the problem of fake news mitigation into the reinforcement learning framework. We develop a policy iteration method unique to the multivariate networked point process, with the goal of optimizing the actions for maximal reward under budget constraints. Our method shows promising performance in real-time intervention experiments on a Twitter network to mitigate a surrogate fake news campaign, and outperforms alternatives on synthetic datasets.

Point processes are powerful tools to model user activities and have a plethora of applications in social sciences. Predicting user activities based on point processes is a central problem. However, existing works are mostly problem specific, use heuristics, or simplify the stochastic nature of point processes. In this paper, we propose a framework that provides an unbiased estimator of the probability mass function of point processes. In particular, we design a key reformulation of the prediction problem, and further derive a differential-difference equation to compute a conditional probability mass function. Our framework is applicable to general point processes and prediction tasks, and achieves superb predictive and efficiency performance in diverse real-world applications compared to state-of-arts.

Point processes are becoming very popular in modeling asynchronous sequential data due to their sound mathematical foundation and strength in modeling a variety of real-world phenomena. Currently, they are often characterized via intensity function which limits model's expressiveness due to unrealistic assumptions on its parametric form used in practice. Furthermore, they are learned via maximum likelihood approach which is prone to failure in multi-modal distributions of sequences. In this paper, we propose an intensity-free approach for point processes modeling that transforms nuisance processes to a target one. Furthermore, we train the model using a likelihood-free leveraging Wasserstein distance between point processes. Experiments on various synthetic and real-world data substantiate the superiority of the proposed point process model over conventional ones.

We analyze the convergence of a decentralized consensus algorithm with delayed gradient information across the network. The nodes in the network privately hold parts of the objective function and collaboratively solve for the consensus optimal solution of the total objective while they can only communicate with their immediate neighbors. In real-world networks, it is often difficult and sometimes impossible to synchronize the nodes, and therefore they have to use stale gradient information during computations. We show that, as long as the random delays are bounded in expectation and a proper diminishing step size policy is employed, the iterates generated by decentralized gradient descent method still converge to a consensual optimal solution. Convergence rates of both objective and consensus are derived. Numerical results on a variety of consensus optimization problems are presented to show the performance of the method.

We consider control problems for multi-stage campaigning over social networks. The dynamic programming framework is employed to balance the high present reward and large penalty on low future outcome in the presence of extensive uncertainties. In particular, we establish theoretical foundations of optimal campaigning over social networks where the user activities are modeled as a multivariate Hawkes process, and we derive a time dependent linear relation between the intensity of exogenous events and several commonly used objective functions of campaigning. We further develop a convex dynamic programming framework for determining the optimal intervention policy that prescribes the required level of external drive at each stage for the desired campaigning result. Experiments on both synthetic data and the real-world MemeTracker dataset show that our algorithm can steer the user activities for optimal campaigning much more accurately than baselines.

We consider the decentralized consensus optimization problem arising from in-situ seismic tomography in large-scale sensor networks. Unlike traditional seismic imaging performed in a centralized location, each node in this setting privately holds an objective function and partial data. The goal of each node is to obtain the optimal solution of the whole seismic image, while communicating only with its immediate neighbors. We present a fast decentralized gradient descent method and prove that this new method can reach optimal convergence rate of O(1/k2) where k is the number of communication/iteration rounds. Extensive numerical experiments on synthetic and real-world sensor network seismic data demonstrate that the proposed algorithms significantly outperform existing methods.

We develop a variational model and a faster and robust numerical algorithm for simultaneous sensitivity map estimation and image reconstruction in partially parallel MR imaging with significantly under-sampled data. The proposed model uses a maximum likelihood approach to minimizing the residue of data fitting in the presence of independent Gaussian noise. The usage of maximum likelihood estimation dramatically reduces the sensitivity to the selection of model parameter, and increases the accuracy and robustness of the algorithm. Moreover, variable splitting based on the specific structure of the objective function, and alternating direction method of multipliers (ADMM) are used to accelerate the computation. The preliminary results indicate that the proposed method resulted in fast and robust reconstruction.

This paper presents a variational model for simultaneous multiphase segmentation and intensity bias estimation for images corrupted by strong noise and intensity inhomogeneity. Since the pixel intensities are not reliable samples for region statistics due to the presence of noise and intensity bias, we use local information based on the joint density within image patches to perform image partition. Hence, the pixel intensity has a multiplicative distribution structure. Then, the maximum-a-posteriori (MAP) principle with those pixel density functions generates the model. To tackle the computational problem of the resultant nonsmooth nonconvex minimization, we relax the constraint on the characteristic functions of partition regions, and apply primal-dual alternating gradient projections to construct a very efficient numerical algorithm. We show that all the variables have closed-form solutions in each iteration, and the computation complexity is very low. In particular, the algorithm involves only regular convolutions and pointwise projections onto the unit ball and canonical simplex. Numerical tests on a variety of images demonstrate that the proposed algorithm is robust, stable, and attains significant improvements on accuracy and efficiency over the state-of-the-arts.

A new algorithm is presented for efficiently solving image reconstruction problems that arise in partially parallel magnetic resonance imaging. This algorithm minimizes an objective function of the form φ(Bu) + 1/2||FpSu - f||2, where φ is the regularization term which may be nonsmooth. In image reconstruction, the φ term corresponds to total variation smoothing and/or L1 regularization term. The least square term 1/2||FpSu - f||2is the fidelity term. In our application, f represents undersampled data from a partially parallel imaging (PPI) system. The proposed algorithm is a generalization of the Bregman operator splitting algorithm with variable stepsize (BOSVS) in which the previous Barzilai-Borwein (BB) step is replaced by a cyclic BB (CBB) step, and an L1 term Ψ is added to the energy function. Experimental results on clinical partially parallel imaging data are given.

In this paper, we present a multiphase segmentation model for MR images in the presence of strong intensity inhomogeneity. The problem is formalized as a constraint min-max optimization problem that consists both primal and dual variables. We use the primal dual hybrid gradient (PDHG) algorithm to alternately solve for the optimal solutions. The proposed algorithm is quite efficient in that all the subproblems have closed form solutions. Moreover, the computational complexity is shown to be linear with respect to the size of the image. Numerical experiments on various images demonstrated that our algorithm outperforms recently developed methods in terms of efficiency and accuracy.

This paper presents two fast algorithms for total variation–based image reconstruction in a magnetic resonance imaging technique known as partially parallel imaging (PPI), where the inversion matrix is large and ill-conditioned. These algorithms utilize variable splitting techniques to decouple the original problem into more easily solved subproblems. The first method reduces the image reconstruction problem to an unconstrained minimization problem, which is solved by an alternating proximal minimization algorithm. One phase of the algorithm solves a total variation (TV) denoising problem, and the second phase solves an ill-conditioned linear system. Linear and sublinear convergence results are given, and an implementation based on a primal-dual hybrid gradient (PDHG) scheme for the TV problem and on a Barzilai–Borwein scheme for the linear inversion is proposed. The second algorithm exploits the special structure of the PPI reconstruction problem by decomposing it into one subproblem involving Fourier transforms and another subproblem that can be treated by the PDHG scheme. Numerical results and comparisons with recently developed methods indicate the efficiency of the proposed algorithms.

Classification is one of the core problems in Computer-Aided Diagnosis (CAD), targeting for early cancer detection using 3D medical imaging interpretation. High detection sensitivity with desirably low false positive (FP) rate is critical for a CAD system to be accepted as a valuable or even indispensable tool in radiologists' workflow. Given various spurious imagery noises which cause observation uncertainties, this remains a very challenging task. In this paper, we propose a novel, two-tiered coarse-to-fine (CTF) classification cascade framework to tackle this problem. We first obtain classification-critical data samples (e.g., implicit samples on the decision boundary) extracted from the holistic data distributions using a robust parametric model (e.g., [13]); then we build a graph-embedding based nonparametric classifier on sampled data, which can more accurately preserve or formulate the complex classification boundary. These two steps can also be considered as effective "sample pruning" and "feature pursuing + kNN/template matching", respectively. Our approach is validated comprehensively in colorectal polyp detection and lung nodule detection CAD systems, as the top two deadly cancers, using hospital scale, multi-site clinical datasets. The results show that our method achieves overall better classification/detection performance than existing state-of-the-art algorithms using single-layer classifiers, such as the support vector machine variants [17], boosting [15], logistic regression [11], relevance vector machine [13], k-nearest neighbor [9] or spectral projections on graph [2].

In this paper, we present a fast numerical algorithm for solving total variation and l(1) (TVL1) based image reconstruction with application in partially parallel magnetic resonance imaging. Our algorithm uses variable splitting method to reduce computational cost. Moreover, the Barzilai-Borwein step size selection method is adopted in our algorithm for much faster convergence. Experimental results on clinical partially parallel imaging data demonstrate that the proposed algorithm requires much fewer iterations and/or less computational cost than recently developed operator splitting and Bregman operator splitting methods, which can deal with a general sensing matrix in reconstruction framework, to get similar or even better quality of reconstructed images.

Both acquisition and reconstruction speed are crucial for magnetic resonance (MR) imaging in clinical applications. In this paper, we present a fast reconstruction algorithm for SENSE in partially parallel MR imaging with arbitrary k-space trajectories. The proposed method is a combination of variable splitting, the classical penalty technique and the optimal gradient method. Variable splitting and the penalty technique reformulate the SENSE model with sparsity regularization as an unconstrained minimization problem, which can be solved by alternating two simple minimizations: One is the total variation and wavelet based denoising that can be quickly solved by several recent numerical methods, whereas the other one involves a linear inversion which is solved by the optimal first order gradient method in our algorithm to significantly improve the performance. Comparisons with several recent parallel imaging algorithms indicate that the proposed method significantly improves the computation efficiency and achieves state-of-the-art reconstruction quality.

In this paper, we propose a segmentation assisted registration model. It partitions the domain of images into several regions such that the residue image in each region is identically distributed with zero mean and variance to be optimized. In this model, we minimize an energy that combines negative log-likelihood of the residue in each region, smoothness of the deformation field and length of the partition curve. It can be viewed as a generalization of the sum of squared difference model and global Gaussian model where the variance is a constant in the entire domain. By taking different variances in different regions, the registration becomes more efficient and accurate, which are demonstrated by the experiments on synthetic and clinical data.