-
Due to the size of data and the limited data storage space in a single local
computer, data can often be stored in a distributed manner. In order to use the
distributed big data in machine learning, performing large-scale machine
learning from the distributed data through communication networks is
inevitable. In this paper, we investigate the impact of network communication
constraints on the convergence speed of distributed machine learning
optimization algorithms. Firstly, we study the convergence rate of the
distributed dual coordinate ascent in a general tree structured network, since
every connected communication network can have a spanning tree, and a tree
network can be understood as the generalization of a star network. Secondly, by
considering network communication delays, we optimize the network-constrained
dual coordinate ascent to maximize its convergence speed in terms of operation
time. Through numerical experiments, we demonstrate that under different
network communication delays, the delay-dependent number of local and global
iterations in distributed dual coordinated ascent can play a significant role
in the achievement of maximum convergence speed.
-
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.