Due to the big size of data and limited data storage volume of a single computer or a single server, data are often stored in a distributed manner. Thus, performing large-scale machine learning operations with the distributed datasets through communication networks is often required. In this paper, we investigate the impact of network communication constraints on the convergence speed of the communication-efficient distributed machine learning algorithm. Firstly, we study the convergence rate of the distributed dual coordinate ascent algorithm in a general tree-structured network. Since a tree network model can be understood as the generalization of a star network model, our algorithm can be thought of as the generalization of the distributed dual coordinate ascent in a star network model. Secondly, by considering network communication delays, we optimize the network-constrained distributed dual coordinate ascent algorithm to maximize its convergence speed. In numerical experiments, we consider machine learning scenarios over communication networks, where local workers cannot directly reach to a central node due to constraints in communication, and demonstrate that the usability of our distributed dual coordinate ascent algorithm in tree networks.

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. In this paper, we propose new polynomial-time algorithms to establish upper bounds of the proportion parameter. We leverage on these techniques to find upper bounds and further develop a new procedure - tree search algorithm - that is able to precisely and quickly verify the null space condition. Numerical experiments show that the execution speed and accuracy of the results obtained from our methods far exceed those of the previous methods which rely on Linear Programming (LP) relaxation and Semidefinite Programming (SDP).

Purpose: To provide a fast computational method, based on the proximal graph solver (POGS) - a convex optimization solver using the alternating direction method of multipliers (ADMM), for calculating an optimal treatment plan in rotating shield brachytherapy (RSBT). RSBT treatment planning has more degrees of freedom than conventional high-dose-rate brachytherapy (HDR-BT) due to the addition of emission direction, and this necessitates a fast optimization technique to enable clinical usage. // Methods: The multi-helix RSBT (H-RSBT) delivery technique was considered with five representative cervical cancer patients. Treatment plans were generated for all patients using the POGS method and the previously considered commercial solver IBM CPLEX. The rectum, bladder, sigmoid, high-risk clinical target volume (HR-CTV), and HR-CTV boundary were the structures considered in our optimization problem, called the asymmetric dose-volume optimization with smoothness control. Dose calculation resolution was 1x1x3 mm^3 for all cases. The H-RSBT applicator has 6 helices, with 33.3 mm of translation along the applicator per helical rotation and 1.7 mm spacing between dwell positions, yielding 17.5 degree emission angle spacing per 5 mm along the applicator.// Results: For each patient, HR-CTV D90, HR-CTV D100, rectum D2cc, sigmoid D2cc, and bladder D2cc matched within 1% for CPLEX and POGS. Also, we obtained similar EQD2 figures between CPLEX and POGS. POGS was around 18 times faster than CPLEX. Over all patients, total optimization times were 32.1-65.4 seconds for CPLEX and 2.1-3.9 seconds for POGS. // Conclusions: POGS substantially reduced treatment plan optimization time around 18 times for RSBT with similar HR-CTV D90, OAR D2cc values, and EQD2 figure relative to CPLEX, which is significant progress toward clinical translation of RSBT. POGS is also applicable to conventional HDR-BT.

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. This work extends the recent work of Jaganathan et al. [1], which considered phaseless super-resolution for discrete signals on the grid.

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. For our error exponent characterization, we introduce the notions of inner conditional Chernoff information and outer conditional Chernoff information. It is demonstrated that mixed observations can strictly improve the error exponents of hypothesis testing, over separate observations of individual random variables. We further characterize the optimal sensing vector maximizing the error exponents, which leads to explicit constructions of the optimal mixed observations in special cases of hypothesis testing for Gaussian random variables. These results show that mixed observations of random variables can reduce the number of required samples in hypothesis testing applications. In order to solve large-scale hypothesis testing problems, we also propose efficient algorithms - LASSO based and message passing based hypothesis testing algorithms.

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. Numerical results demonstrate that our block iterative reweighted methods provide both better recovery performance and faster speed than other known methods.

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. We devise a general semidefinite program to recover these frequencies using theories of positive trigonometric polynomials. Our theoretical analysis shows that, given sufficient prior information, perfect signal reconstruction is possible using signal samples no more than thrice the number of signal frequencies. Numerical experiments demonstrate great performance enhancements using our method. We show that the nominal resolution necessary for the grid-free results can be improved if prior information is suitably employed.

The Gemini Planet Imager (GPI) entered on-sky commissioning and had its first-light at the Gemini South (GS) telescope in November 2013. GPI is an extreme adaptive optics (XAO), high-contrast imager and integral-field spectrograph dedicated to the direct detection of hot exo-planets down to a Jupiter mass. The performance of the apodized pupil Lyot coronagraph depends critically upon the residual wavefront error (design goal of 60 nm RMS with 5 mas RMS tip/tilt), and therefore is most sensitive to vibration (internal or external) of Gemini's instrument suite. Excess vibration can be mitigated by a variety of methods such as passive or active dampening at the instrument or telescope structure or Kalman filtering of specific frequencies with the AO control loop. Understanding the sources, magnitudes and impact of vibration is key to mitigation. This paper gives an overview of related investigations based on instrument data (GPI AO module) as well as external data from accelerometer sensors placed at different locations on the GS telescope structure. We report the status of related mitigation efforts, and present corresponding results.

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. The proposed semidefinite program achieves super-resolution frequency recovery by taking advantage of known structures of frequency blocks. Numerical experiments show great performance enhancements using our method.

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. In this paper, we settle this problem by proposing equivalent semidefinite programming formulations of atomic norm minimization to recover signals with $d$-dimensional ($d\geq 2$) off-the-grid frequencies.

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. Our results show that equipping off-the-grid CS with the known-poles algorithm can increase the probability of recovering all the frequency components.

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,...,n\}$, and $|K|$ is the cardinality of $K$. In particular, we are interested in finding the maximum $k$ such that $\alpha_k < {1}{2}$. However, computing $\alpha_k$ is known to be extremely challenging. In this paper, we first propose a series of new polynomial-time algorithms to compute upper bounds on $\alpha_k$. Based on these new polynomial-time algorithms, we further design a new sandwiching algorithm, to compute the \emph{exact} $\alpha_k$ with greatly reduced complexity. When needed, this new sandwiching algorithm also achieves a smooth tradeoff between computational complexity and result accuracy. Empirical results show the performance improvements of our algorithm over existing known methods; and our algorithm outputs precise values of $\alpha_k$, with much lower complexity than exhaustive search.

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$. However, for signals whose nonzero elements are strictly suspended from zero in distribution (for example, constant-modulus, only taking values `$+d$' or `$-d$' for some nonzero real number $d$), no polynomial-time signal recovery algorithms were known to provide better phase transition performance than plain $\ell_1$ minimization, especially for dense sensing matrices. In this paper, we show that a polynomial-time algorithm can universally elevate the phase-transition performance of compressed sensing, compared with $\ell_1$ minimization, even for signals with constant-modulus nonzero elements. Contrary to conventional wisdoms that compressed sensing matrices are desired to be isometric, we show that non-isometric matrices are not necessarily bad sensing matrices. In this paper, we also provide a framework for recovering sparse signals when sensing matrices are not isometric.

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. We reduce this problem of system identification to a sparse error correcting problem using a Toeplitz structured real-numbered coding matrix. We prove the performance guarantee of Toeplitz structured matrix in sparse error correction. Thresholds on the percentage of correctable errors for Toeplitz structured matrices are established. When both outliers and observation noise are present, we have shown that the estimation error goes to 0 asymptotically as long as the probability density function for observation noise is not "vanishing" around 0. No probabilistic assumptions are imposed on the outliers.

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. We reduce this problem of system identification to a sparse error correcting problem using a Toeplitz structured real-numbered coding matrix. We prove the performance guarantee of Toeplitz structured matrix in sparse error correction. Thresholds on the percentage of correctable errors for Toeplitz structured matrices are also established. When both outliers and observation noise are present, we have shown that the estimation error goes to 0 asymptotically as long as the probability density function for observation noise is not "vanishing" around 0.