
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 largescale 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 communicationefficient distributed machine learning algorithm.
Firstly, we study the convergence rate of the distributed dual coordinate
ascent algorithm in a general treestructured 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 networkconstrained 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 polynomialtime 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 highdoserate brachytherapy (HDRBT) due to the
addition of emission direction, and this necessitates a fast optimization
technique to enable clinical usage. // Methods: The multihelix RSBT (HRSBT)
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, highrisk clinical target volume (HRCTV), and HRCTV boundary were
the structures considered in our optimization problem, called the asymmetric
dosevolume optimization with smoothness control. Dose calculation resolution
was 1x1x3 mm^3 for all cases. The HRSBT 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, HRCTV D90, HRCTV 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.165.4 seconds for CPLEX and 2.13.9 seconds for POGS. // Conclusions:
POGS substantially reduced treatment plan optimization time around 18 times for
RSBT with similar HRCTV 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 HDRBT.

Phaseless superresolution refers to the problem of superresolving a signal
from only its lowfrequency Fourier magnitude measurements. In this paper, we
consider the phaseless superresolution problem of recovering a sum of sparse
Dirac delta functions which can be located anywhere in the continuous
timedomain. 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 superresolution 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 $(nk)$
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 timeinvariant mixed
observations, random timevarying mixed observations, and deterministic
timevarying 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 largescale 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 continuousvalued 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 continuousvalued
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 superresolution 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
gridfree results can be improved if prior information is suitably employed.

The Gemini Planet Imager (GPI) entered onsky commissioning and had its
firstlight at the Gemini South (GS) telescope in November 2013. GPI is an
extreme adaptive optics (XAO), highcontrast imager and integralfield
spectrograph dedicated to the direct detection of hot exoplanets 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 superresolution 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
continuousvalued frequencies using theories of positive trigonometric
polynomials. The proposed semidefinite program achieves superresolution
frequency recovery by taking advantage of known structures of frequency blocks.
Numerical experiments show great performance enhancements using our method.

Recent research in offthegrid compressed sensing (CS) has demonstrated
that, under certain conditions, one can successfully recover a spectrally
sparse signal from a few timedomain 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$) offthegrid 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$) offthegrid
frequencies.

Recent research in offthegrid compressed sensing (CS) has demonstrated
that, under certain conditions, one can successfully recover a spectrally
sparse signal from a few timedomain samples even though the dictionary is
continuous. In this paper, we extend offthegrid 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
offthegrid CS with the knownpoles 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 $(nm) \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 polynomialtime algorithms to compute upper bounds on $\alpha_k$. Based on
these new polynomialtime 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 polynomialtime algorithms. It is of great theoretical and
practical interest to find alternative polynomialtime 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 twostage reweighted $\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,
constantmodulus, only taking values `$+d$' or `$d$' for some nonzero real
number $d$), no polynomialtime 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
polynomialtime algorithm can universally elevate the phasetransition
performance of compressed sensing, compared with $\ell_1$ minimization, even
for signals with constantmodulus nonzero elements. Contrary to conventional
wisdoms that compressed sensing matrices are desired to be isometric, we show
that nonisometric 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 realnumbered
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 realnumbered
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.