# Weiyu Xu

## Contact Details

NameWeiyu Xu |
||

Affiliation |
||

Location |
||

## Pubs By Year |
||

## Pub CategoriesComputer Science - Information Theory (49) Mathematics - Information Theory (49) Mathematics - Optimization and Control (9) Computer Science - Learning (6) Statistics - Machine Learning (6) Computer Science - Discrete Mathematics (3) Computer Science - Networking and Internet Architecture (3) Statistics - Computation (1) Computer Science - Performance (1) Mathematics - Probability (1) Mathematics - Numerical Analysis (1) Computer Science - Distributed; Parallel; and Cluster Computing (1) Computer Science - Computer Vision and Pattern Recognition (1) |

## Publications Authored By Weiyu Xu

With explosion of data size and limited storage space at a single location, data are often distributed at different locations. We thus face the challenge of performing large-scale machine learning from these distributed data through communication networks. In this paper, we study how the network communication constraints will impact the convergence speed of distributed machine learning optimization algorithms. Read More

Phaseless super-resolution refers to the problem of superresolving a signal from only its low-frequency Fourier magnitude measurements. In this paper, we consider the phaseless super-resolution problem of recovering a sum of sparse Dirac delta functions which can be located anywhere in the continuous time-domain. For such signals in the continuous domain, we propose a novel Semidefinite Programming (SDP) based signal recovery method to achieve the phaseless superresolution. Read More

In this paper, we study the problem of determining $k$ anomalous random variables that have different probability distributions from the rest $(n-k)$ random variables. Instead of sampling each individual random variable separately as in the conventional hypothesis testing, we propose to perform hypothesis testing using mixed observations that are functions of multiple random variables. We characterize the error exponents for correctly identifying the $k$ anomalous random variables under fixed time-invariant mixed observations, random time-varying mixed observations, and deterministic time-varying mixed observations. Read More

The null space condition for $\ell_1$ minimization in compressed sensing is a necessary and sufficient condition on the sensing matrices under which a sparse signal can be uniquely recovered from the observation data via $\ell_1$ minimization. However, verifying the null space condition is known to be computationally challenging. Most of the existing methods can provide only upper and lower bounds on the proportion parameter that characterizes the null space condition. Read More

In this paper, we propose an efficient optimal joint channel estimation and data detection algorithm for massive MIMO wireless systems. Our algorithm is optimal in terms of the generalized likelihood ratio test (GLRT). For massive MIMO systems, we show that the expected complexity of our algorithm grows polynomially in the channel coherence time. Read More

We study the problem of recovering an $n$-dimensional vector of $\{\pm1\}^n$ (BPSK) signals from $m$ noise corrupted measurements $\mathbf{y}=\mathbf{A}\mathbf{x}_0+\mathbf{z}$. In particular, we consider the box relaxation method which relaxes the discrete set $\{\pm1\}^n$ to the convex set $[-1,1]^n$ to obtain a convex optimization algorithm followed by hard thresholding. When the noise $\mathbf{z}$ and measurement matrix $\mathbf{A}$ have iid standard normal entries, we obtain an exact expression for the bit-wise probability of error $P_e$ in the limit of $n$ and $m$ growing and $\frac{m}{n}$ fixed. Read More

Characterizing the phase transitions of convex optimizations in recovering structured signals or data is of central importance in compressed sensing, machine learning and statistics. The phase transitions of many convex optimization signal recovery methods such as $\ell_1$ minimization and nuclear norm minimization are well understood through recent years' research. However, rigorously characterizing the phase transition of total variation (TV) minimization in recovering sparse-gradient signal is still open. Read More

We propose novel algorithms that enhance the performance of recovering unknown continuous-valued frequencies from undersampled signals. Our iterative reweighted frequency recovery algorithms employ the support knowledge gained from earlier steps of our algorithms as block prior information to enhance frequency recovery. Our methods improve the performance of the atomic norm minimization which is a useful heuristic in recovering continuous-valued frequency contents. Read More

Massive MIMO communication systems, by virtue of utilizing very large number of antennas, have a potential to yield higher spectral and energy efficiency in comparison with the conventional MIMO systems. In this paper, we consider uplink channel estimation in massive MIMO-OFDM systems with frequency selective channels. With increased number of antennas, the channel estimation problem becomes very challenging as exceptionally large number of channel parameters have to be estimated. Read More

This paper considers reconstructing a spectrally sparse signal from a small number of randomly observed time-domain samples. The signal of interest is a linear combination of complex sinusoids at $R$ distinct frequencies. The frequencies can assume any continuous values in the normalized frequency domain $[0,1)$. Read More

Massive MIMO systems can greatly increase spectral and energy efficiency over traditional MIMO systems by exploiting large antenna arrays. However, increasing the number of antennas at the base station (BS) makes the uplink non-coherent data detection very challenging in massive MIMO systems. In this paper we consider the joint maximum likelihood (ML) channel estimation and data detection problem for massive SIMO (single input multiple output) wireless systems, which is a special case of wireless systems with large antenna arrays. Read More

This paper explores robust recovery of a superposition of $R$ distinct complex exponential functions from a few random Gaussian projections. We assume that the signal of interest is of $2N-1$ dimensional and $R<<2N-1$. This framework covers a large class of signals arising from real applications in biology, automation, imaging science, etc. Read More

Massive MIMO systems have made significant progress in increasing spectral and energy efficiency over traditional MIMO systems by exploiting large antenna arrays. In this paper we consider the joint maximum likelihood (ML) channel estimation and data detection problem for massive SIMO (single input multiple output) wireless systems. Despite the large number of unknown channel coefficients for massive SIMO systems, we improve an algorithm to achieve the exact ML non-coherent data detection with a low expected complexity. Read More

We address the problem of super-resolution frequency recovery using prior knowledge of the structure of a spectrally sparse, undersampled signal. In many applications of interest, some structure information about the signal spectrum is often known. The prior information might be simply knowing precisely some signal frequencies or the likelihood of a particular frequency component in the signal. Read More

We address the problem of super-resolution line spectrum estimation of an undersampled signal with block prior information. The component frequencies of the signal are assumed to take arbitrary continuous values in known frequency blocks. We formulate a general semidefinite program to recover these continuous-valued frequencies using theories of positive trigonometric polynomials. Read More

The problem of sequentially finding an independent and identically distributed (i.i.d. Read More

Recent research in off-the-grid compressed sensing (CS) has demonstrated that, under certain conditions, one can successfully recover a spectrally sparse signal from a few time-domain samples even though the dictionary is continuous. In particular, atomic norm minimization was proposed in \cite{tang2012csotg} to recover $1$-dimensional spectrally sparse signal. However, in spite of existing research efforts \cite{chi2013compressive}, it was still an open problem how to formulate an equivalent positive semidefinite program for atomic norm minimization in recovering signals with $d$-dimensional ($d\geq 2$) off-the-grid frequencies. Read More

Recent research in off-the-grid compressed sensing (CS) has demonstrated that, under certain conditions, one can successfully recover a spectrally sparse signal from a few time-domain samples even though the dictionary is continuous. In this paper, we extend off-the-grid CS to applications where some prior information about spectrally sparse signal is known. We specifically consider cases where a few contributing frequencies or poles, but not their amplitudes or phases, are known a priori. Read More

In this paper we introduce an optimized Markov Chain Monte Carlo (MCMC) technique for solving the integer least-squares (ILS) problems, which include Maximum Likelihood (ML) detection in Multiple-Input Multiple-Output (MIMO) systems. Two factors contribute to the speed of finding the optimal solution by the MCMC detector: the probability of the optimal solution in the stationary distribution, and the mixing time of the MCMC detector. Firstly, we compute the optimal value of the "temperature" parameter, in the sense that the temperature has the desirable property that once the Markov chain has mixed to its stationary distribution, there is polynomially small probability ($1/\mbox{poly}(N)$, instead of exponentially small) of encountering the optimal solution. Read More

In compressed sensing problems, $\ell_1$ minimization or Basis Pursuit was known to have the best provable phase transition performance of recoverable sparsity among polynomial-time algorithms. It is of great theoretical and practical interest to find alternative polynomial-time algorithms which perform better than $\ell_1$ minimization. \cite{Icassp reweighted l_1}, \cite{Isit reweighted l_1}, \cite{XuScaingLaw} and \cite{iterativereweightedjournal} have shown that a two-stage re-weighted $\ell_1$ minimization algorithm can boost the phase transition performance for signals whose nonzero elements follow an amplitude probability density function (pdf) $f(\cdot)$ whose $t$-th derivative $f^{t}(0) \neq 0$ for some integer $t \geq 0$. Read More

In this paper, we propose new efficient algorithms to verify the null space condition in compressed sensing (CS). Given an $(n-m) \times n$ ($m>0$) CS matrix $A$ and a positive $k$, we are interested in computing $\displaystyle \alpha_k = \max_{\{z: Az=0,z\neq 0\}}\max_{\{K: |K|\leq k\}}$ ${\|z_K \|_{1}}{\|z\|_{1}}$, where $K$ represents subsets of $\{1,2,.. Read More

The problem of sequentially finding an independent and identically distributed (i.i.d. Read More

In this paper, we consider using total variation minimization to recover signals whose gradients have a sparse support, from a small number of measurements. We establish the proof for the performance guarantee of total variation (TV) minimization in recovering \emph{one-dimensional} signal with sparse gradient support. This partially answers the open problem of proving the fidelity of total variation minimization in such a setting \cite{TVMulti}. Read More

We design optimal $2 \times N$ ($2

In this paper, we consider robust system identification under sparse outliers and random noises. In our problem, system parameters are observed through a Toeplitz matrix. All observations are subject to random noises and a few are corrupted with outliers. Read More

In this paper, we study the hypothesis testing problem of, among $n$ random variables, determining $k$ random variables which have different probability distributions from the rest $(n-k)$ random variables. Instead of using separate measurements of each individual random variable, we propose to use mixed measurements which are functions of multiple random variables. It is demonstrated that $O({\displaystyle \frac{k \log(n)}{\min_{P_i, P_j} C(P_i, P_j)}})$ observations are sufficient for correctly identifying the $k$ anomalous random variables with high probability, where $C(P_i, P_j)$ is the Chernoff information between two possible distributions $P_i$ and $P_j$ for the proposed mixed observations. Read More

In this paper, we consider robust system identification under sparse outliers and random noises. In this problem, system parameters are observed through a Toeplitz matrix. All observations are subject to random noises and a few are corrupted with outliers. Read More

This paper proposes a low-complexity algorithm for blind equalization of data in OFDM-based wireless systems with general constellations. The proposed algorithm is able to recover data even when the channel changes on a symbol-by-symbol basis, making it suitable for fast fading channels. The proposed algorithm does not require any statistical information of the channel and thus does not suffer from latency normally associated with blind methods. Read More

Sparse recovery can recover sparse signals from a set of underdetermined linear measurements. Motivated by the need to monitor large-scale networks from a limited number of measurements, this paper addresses the problem of recovering sparse signals in the presence of network topological constraints. Unlike conventional sparse recovery where a measurement can contain any subset of the unknown variables, we use a graph to characterize the topological constraints and allow an additive measurement over nodes (unknown variables) only if they induce a connected subgraph. Read More

We consider the problem of designing optimal $M \times N$ ($M \leq N$) sensing matrices which minimize the maximum condition number of all the submatrices of $K$ columns. Such matrices minimize the worst-case estimation errors when only $K$ sensors out of $N$ sensors are available for sensing at a given time. For M=2 and matrices with unit-normed columns, this problem is equivalent to the problem of maximizing the minimum singular value among all the submatrices of $K$ columns. Read More

In this paper, we study the mixing time of Markov Chain Monte Carlo (MCMC) for integer least-square (LS) optimization problems. It is found that the mixing time of MCMC for integer LS problems depends on the structure of the underlying lattice. More specifically, the mixing time of MCMC is closely related to whether there is a local minimum in the lattice structure. Read More

In this paper, we consider the problem of sparse recovery from nonlinear measurements, which has applications in state estimation and bad data detection for power networks. An iterative mixed $\ell_1$ and $\ell_2$ convex program is used to estimate the true state by locally linearizing the nonlinear measurements. When the measurements are linear, through using the almost Euclidean property for a linear subspace, we derive a new performance bound for the state estimation error under sparse bad data and additive observation noise. Read More

It is well known that $\ell_1$ minimization can be used to recover sufficiently sparse unknown signals from compressed linear measurements. In fact, exact thresholds on the sparsity, as a function of the ratio between the system dimensions, so that with high probability almost all sparse signals can be recovered from i.i. Read More

This paper addresses the problem of sparse recovery with graph constraints in the sense that we can take additive measurements over nodes only if they induce a connected subgraph. We provide explicit measurement constructions for several special graphs. A general measurement construction algorithm is also proposed and evaluated. Read More

In this paper, we consider the problem of state estimation through observations possibly corrupted with both bad data and additive observation noises. A mixed $\ell_1$ and $\ell_2$ convex programming is used to separate both sparse bad data and additive noises from the observations. Through using the almost Euclidean property for a linear subspace, we derive a new performance bound for the state estimation error under sparse bad data and additive observation noises. Read More

It is known that a high-dimensional sparse vector x* in R^n can be recovered
from low-dimensional measurements y= A^{m*n} x* (m

This paper provides analysis to a generalized version of the coupon collector problem, in which the collector gets $d$ distinct coupons each run and she chooses the one that she has the least so far. On the asymptotic case when the number of coupons $n$ goes to infinity, we show that on average $\frac{n\log n}{d} + \frac{n}{d}(m-1)\log\log{n}+O(mn)$ runs are needed to collect $m$ sets of coupons. An efficient exact algorithm is also developed for any finite case to compute the average needed runs exactly. Read More

$\ell_1$ minimization can be used to recover sufficiently sparse unknown signals from compressed linear measurements. In fact, exact thresholds on the sparsity (the size of the support set), under which with high probability a sparse signal can be recovered from i.i. Read More

In this paper we introduce a nonuniform sparsity model and analyze the performance of an optimized weighted $\ell_1$ minimization over that sparsity model. In particular, we focus on a model where the entries of the unknown vector fall into two sets, with entries of each set having a specific probability of being nonzero. We propose a weighted $\ell_1$ minimization recovery algorithm and analyze its performance using a Grassmann angle approach. Read More

In this paper, motivated by network inference and tomography applications, we study the problem of compressive sensing for sparse signal vectors over graphs. In particular, we are interested in recovering sparse vectors representing the properties of the edges from a graph. Unlike existing compressive sensing results, the collective additive measurements we are allowed to take must follow connected paths over the underlying graph. Read More

An unknown vector f in R^n can be recovered from corrupted measurements y = Af + e where A^(m*n)(m>n) is the coding matrix if the unknown error vector e is sparse. We investigate the relationship of the fraction of errors and the recovering ability of lp-minimization (0 < p <= 1) which returns a vector x minimizing the "lp-norm" of y - Ax. We give sharp thresholds of the fraction of errors that determine the successful recovery of f. Read More

$\ell_1$ minimization is often used for finding the sparse solutions of an under-determined linear system. In this paper we focus on finding sharp performance bounds on recovering approximately sparse signals using $\ell_1$ minimization, possibly under noisy measurements. While the restricted isometry property is powerful for the analysis of recovering approximately sparse signals with noisy measurements, the known bounds on the achievable sparsity (The "sparsity" in this paper means the size of the set of nonzero or significant elements in a signal vector. Read More

It is well known that $\ell_1$ minimization can be used to recover sufficiently sparse unknown signals from compressed linear measurements. In fact, exact thresholds on the sparsity, as a function of the ratio between the system dimensions, so that with high probability almost all sparse signals can be recovered from iid Gaussian measurements, have been computed and are referred to as "weak thresholds" \cite{D}. In this paper, we introduce a reweighted $\ell_1$ recovery algorithm composed of two steps: a standard $\ell_1$ minimization step to identify a set of entries where the signal is likely to reside, and a weighted $\ell_1$ minimization step where entries outside this set are penalized. Read More

This paper investigates the uniqueness of a nonnegative vector solution and the uniqueness of a positive semidefinite matrix solution to underdetermined linear systems. A vector solution is the unique solution to an underdetermined linear system only if the measurement matrix has a row-span intersecting the positive orthant. Focusing on two types of binary measurement matrices, Bernoulli 0-1 matrices and adjacency matrices of general expander graphs, we show that, in both cases, the support size of a unique nonnegative solution can grow linearly, namely O(n), with the problem dimension n. Read More

In this paper we study a Markov Chain Monte Carlo (MCMC) Gibbs sampler for solving the integer least-squares problem. In digital communication the problem is equivalent to performing Maximum Likelihood (ML) detection in Multiple-Input Multiple-Output (MIMO) systems. While the use of MCMC methods for such problems has already been proposed, our method is novel in that we optimize the "temperature" parameter so that in steady state, i. Read More

It is now well understood that $\ell_1$ minimization algorithm is able to recover sparse signals from incomplete measurements [2], [1], [3] and sharp recoverable sparsity thresholds have also been obtained for the $\ell_1$ minimization algorithm. However, even though iterative reweighted $\ell_1$ minimization algorithms or related algorithms have been empirically observed to boost the recoverable sparsity thresholds for certain types of signals, no rigorous theoretical results have been established to prove this fact. In this paper, we try to provide a theoretical foundation for analyzing the iterative reweighted $\ell_1$ algorithms. Read More

We investigate the sparse recovery problem of reconstructing a high-dimensional non-negative sparse vector from lower dimensional linear measurements. While much work has focused on dense measurement matrices, sparse measurement schemes are crucial in applications, such as DNA microarrays and sensor networks, where dense measurements are not practically feasible. One possible construction uses the adjacency matrices of expander graphs, which often leads to recovery algorithms much more efficient than $\ell_1$ minimization. Read More

In this paper we study the compressed sensing problem of recovering a sparse signal from a system of underdetermined linear equations when we have prior information about the probability of each entry of the unknown signal being nonzero. In particular, we focus on a model where the entries of the unknown vector fall into two sets, each with a different probability of being nonzero. We propose a weighted $\ell_1$ minimization recovery algorithm and analyze its performance using a Grassman angle approach. Read More

Minimizing the rank of a matrix subject to constraints is a challenging problem that arises in many applications in control theory, machine learning, and discrete geometry. This class of optimization problems, known as rank minimization, is NP-HARD, and for most practical problems there are no efficient algorithms that yield exact solutions. A popular heuristic algorithm replaces the rank function with the nuclear norm--equal to the sum of the singular values--of the decision variable. Read More

Expander graphs have been recently proposed to construct efficient compressed sensing algorithms. In particular, it has been shown that any $n$-dimensional vector that is $k$-sparse (with $k\ll n$) can be fully recovered using $O(k\log\frac{n}{k})$ measurements and only $O(k\log n)$ simple recovery iterations. In this paper we improve upon this result by considering expander graphs with expansion coefficient beyond 3/4 and show that, with the same number of measurements, only $O(k)$ recovery iterations are required, which is a significant improvement when $n$ is large. Read More