Wei Dai

Wei Dai, Olgica Milenkovic

We propose a new method for reconstruction of sparse signals with and without noisy perturbations, termed the subspace pursuit algorithm. The algorithm has two important characteristics: low computational complexity, comparable to that of orthogonal matching pursuit techniques when applied to very sparse signals, and reconstruction accuracy of the same order as that of LP optimization methods. The presented analysis shows that in the noiseless setting, the proposed algorithm can exactly reconstruct arbitrary sparse signals provided that the sensing matrix satisfies the restricted isometry property with a constant parameter. In the noisy setting and in the case that the signal is not exactly sparse, it can be shown that the mean squared error of the reconstruction is upper bounded by constant multiples of the measurement and signal perturbation energies.

Wei Dai, Ely Kerman, Olgica Milenkovic

The low-rank matrix completion problem can be succinctly stated as follows: given a subset of the entries of a matrix, find a low-rank matrix consistent with the observations. While several low-complexity algorithms for matrix completion have been proposed so far, it remains an open problem to devise search procedures with provable performance guarantees for a broad class of matrix models. The standard approach to the problem, which involves the minimization of an objective function defined using the Frobenius metric, has inherent difficulties: the objective function is not continuous and the solution set is not closed. To address this problem, we consider an optimization procedure that searches for a column (or row) space that is geometrically consistent with the partial observations. The geometric objective function is continuous everywhere and the solution set is the closure of the solution set of the Frobenius metric. We also preclude the existence of local minimizers, and hence establish strong performance guarantees, for special completion scenarios, which do not require matrix incoherence or large matrix size.

Jiayi Chen, Yanbiao Ma, Andi Zhang et al.

Visual attribute imbalance is a common yet underexplored issue in image classification, significantly impacting model performance and generalization. In this work, we first define the first-level and second-level attributes of images and then introduce a CLIP-based framework to construct a visual attribute dictionary, enabling automatic evaluation of image attributes. By systematically analyzing both single-attribute imbalance and compositional attribute imbalance, we reveal how the rarity of attributes affects model performance. To tackle these challenges, we propose adjusting the sampling probability of samples based on the rarity of their compositional attributes. This strategy is further integrated with various data augmentation techniques (such as CutMix, Fmix, and SaliencyMix) to enhance the model's ability to represent rare attributes. Extensive experiments on benchmark datasets demonstrate that our method effectively mitigates attribute imbalance, thereby improving the robustness and fairness of deep neural networks. Our research highlights the importance of modeling visual attribute distributions and provides a scalable solution for long-tail image classification tasks.

Cheng Cheng, Wei Dai

Dictionary learning aims at seeking a dictionary under which the training data can be sparsely represented. Methods in the literature typically formulate the dictionary learning problem as an optimization w.r.t. two variables, i.e., dictionary and sparse coefficients, and solve it by alternating between two stages: sparse coding and dictionary update. The key contribution of this work is a Rank-One Atomic Decomposition (ROAD) formulation where dictionary learning is cast as an optimization w.r.t. a single variable which is a set of rank one matrices. The resulting algorithm is hence single-stage. Compared with two-stage algorithms, ROAD minimizes the sparsity of the coefficients whilst keeping the data consistency constraint throughout the whole learning process. An alternating direction method of multipliers (ADMM) is derived to solve the optimization problem and the lower bound of the penalty parameter is computed to guarantees a global convergence despite non-convexity of the optimization formulation. From practical point of view, ROAD reduces the number of tuning parameters required in other benchmark algorithms. Numerical tests demonstrate that ROAD outperforms other benchmark algorithms for both synthetic data and real data, especially when the number of training samples is small.

Cheng Cheng, Wei Dai

Dictionary learning aims to find a dictionary under which the training data can be sparsely represented, and it is usually achieved by iteratively applying two stages: sparse coding and dictionary update. Typical methods for dictionary update focuses on refining both dictionary atoms and their corresponding sparse coefficients by using the sparsity patterns obtained from sparse coding stage, and hence it is a non-convex bilinear inverse problem. In this paper, we propose a Rank-One Matrix Decomposition (ROMD) algorithm to recast this challenge into a convex problem by resolving these two variables into a set of rank-one matrices. Different from methods in the literature, ROMD updates the whole dictionary at a time using convex programming. The advantages hence include both convergence guarantees for dictionary update and faster convergence of the whole dictionary learning. The performance of ROMD is compared with other benchmark dictionary learning algorithms. The results show the improvement of ROMD in recovery accuracy, especially in the cases of high sparsity level and fewer observation data.

Qi Yu, Wei Dai, Zoran Cvetkovic et al.

Algorithms for learning a dictionary to sparsely represent a given dataset typically alternate between sparse coding and dictionary update stages. Methods for dictionary update aim to minimise expansion error by updating dictionary vectors and expansion coefficients given patterns of non-zero coefficients obtained in the sparse coding stage. We propose a block total least squares (BLOTLESS) algorithm for dictionary update. BLOTLESS updates a block of dictionary elements and the corresponding sparse coefficients simultaneously. In the error free case, three necessary conditions for exact recovery are identified. Lower bounds on the number of training data are established so that the necessary conditions hold with high probability. Numerical simulations show that the bounds approximate well the number of training data needed for exact dictionary recovery. Numerical experiments further demonstrate several benefits of dictionary learning with BLOTLESS update compared with state-of-the-art algorithms especially when the amount of training data is small.

Jingyuan Xia, Wei Dai, John Polak et al.

This paper studies the problem of estimating origin-destination (OD) flows from link flows. As the number of link flows is typically much less than that of OD flows, the inverse problem is severely ill-posed and hence prior information is required to recover the ground truth. The basic approach in the literature relies on a forward model where the so called traffic assignment matrix maps OD flows to link flows. Due to the ill-posedness of the problem, prior information on the assignment matrix and OD flows are typically needed. The main contributions of this paper include a dimension reduction of the inquired flows from $O(n^2)$ to $O(n)$, and a demonstration that for the first time the ground truth OD flows can be uniquely identified with no or little prior information. To cope with the ill-posedness due to the large number of unknowns, a new forward model is developed which does not involve OD flows directly but is built upon the flows characterized only by their origins, henceforth referred as O-flows. The new model preserves all the OD information and more importantly reduces the dimension of the inverse problem substantially. A Gauss-Seidel method is deployed to solve the inverse problem, and a necessary condition for the uniqueness of the solution is proved. Simulations demonstrate that blind estimation where no prior information is available is possible for some network settings. Some challenging network settings are identified and discussed, where a remedy based on temporal patterns of the O-flows is developed and numerically shown effective.

Jinliang Wei, Wei Dai, Abhimanu Kumar et al.

In distributed ML applications, shared parameters are usually replicated among computing nodes to minimize network overhead. Therefore, proper consistency model must be carefully chosen to ensure algorithm's correctness and provide high throughput. Existing consistency models used in general-purpose databases and modern distributed ML systems are either too loose to guarantee correctness of the ML algorithms or too strict and thus fail to fully exploit the computing power of the underlying distributed system. Many ML algorithms fall into the category of \emph{iterative convergent algorithms} which start from a randomly chosen initial point and converge to optima by repeating iteratively a set of procedures. We've found that many such algorithms are to a bounded amount of inconsistency and still converge correctly. This property allows distributed ML to relax strict consistency models to improve system performance while theoretically guarantees algorithmic correctness. In this paper, we present several relaxed consistency models for asynchronous parallel computation and theoretically prove their algorithmic correctness. The proposed consistency models are implemented in a distributed parameter server and evaluated in the context of a popular ML application: topic modeling.