Search

Wasserstein balls, which contain all probability measures within a pre-specified Wasserstein distance to a reference measure, have recently enjoyed wide popularity in the distributionally robust optimization and machine learning communities to formulate and solve data-driven optimization problems with rigorous statistical guarantees. In this technical note we prove that the Wasserstein ball is weakly compact under mild conditions, and we offer necessary and sufficient conditions for the existence of optimal solutions. We also characterize the sparsity of solutions if the Wasserstein ball is centred at a discrete reference measure. In comparison with the existing literature, which has proved similar results under different conditions, our proofs are self-contained and shorter, yet mathematically rigorous, and our necessary and sufficient conditions for the existence of optimal solutions are easily verifiable in practice.

Recent advancements in the throughput of next-generation sequencing machines pose a huge computational challenge in analyzing the massive quantities of sequenced data produced. A critical initial step of genomic data analysis is short read alignment, which is a bottleneck in the analysis workflow. This paper explores the use of a reconfigurable architecture to accelerate this process, based on the seed-and-extend model of Bowtie2. In the proposed approach, complete information available in sequencing data is integrated into an FPGA alignment pipeline for biologically accurate runtime acceleration. Experimental results show that our architecture achieves a similar alignment rate compared to Bowtie2, mapping reads around twice as fast. Particularly, the alignment time is reduced from 50 minutes to 26 minutes when processing 300M reads.

We propose a new family of inexact sequential quadratic approximation (SQA) methods, which we call the inexact regularized proximal Newton (IRPN) method, for minimizing the sum of two closed proper convex functions, one of which is smooth and the other is possibly non-smooth. Our proposed method features strong convergence guarantees even when applied to problems with degenerate solutions while allowing the inner minimization to be solved inexactly. Specifically, we prove that when the problem possesses the so-called Luo–Tseng error bound (EB) property, IRPN converges globally to an optimal solution, and the local convergence rate of the sequence of iterates generated by IRPN is linear, superlinear, or even quadratic, depending on the choice of parameters of the algorithm. Prior to this work, such EB property has been extensively used to establish the linear convergence of various first-order methods. However, to the best of our knowledge, this work is the first to use the Luo–Tseng EB property to establish the superlinear convergence of SQA-type methods for non-smooth convex minimization. As a consequence of our result, IRPN is capable of solving regularized regression or classification problems under the high-dimensional setting with provable convergence guarantees. We compare our proposed IRPN with several empirically efficient algorithms by applying them to the $$\ell _1$$ -regularized logistic regression problem. Experiment results show the competitiveness of our proposed method.

This paper studies a robust design problem for far-field line-of-sight (LOS) channels where phase errors are present. Compared with the commonly used additive error model, the phase error model is more suitable for capturing the uncertainty in an LOS channel, as the dominant source of uncertainty lies in the phase. We consider a multiple-input single-output (MISO) multicast scenario, in which our goal is to design a beamformer that minimizes the transmit power while satisfying probabilistic signal-to-noise ratio (SNR) constraints. The probabilistic constraints give rise to a new computational challenge, as they involve random trigonometric forms. In this work, we propose to first approximate the random trigonometric form by its second-order Taylor expansion and then tackle the resulting random quadratic form using a Bernstein-type inequality. The advantage of such an approach is that an approximately optimal beamformer can be obtained using the standard semidefinite relaxation technique. In the simulations, we first show that if a non-robust design (i.e., one that does not take phase errors into account) is used, then the whole system may collapse. We then show that our proposed method is less conservative than the existing robust design based on Gaussian approximation and thus requires a lower power budget., Comment: This manuscript is submitted for possible journal publication on 13-Nov-2015

In this paper, we establish the following perturbation result concerning the singular values of a matrix: Let A , B ∈ R m × n be given matrices, and let f : R + → R + be a concave function satisfying f ( 0 ) = 0 . Then, we have ∑ i = 1 min ⁡ { m , n } | f ( σ i ( A ) ) − f ( σ i ( B ) ) | ≤ ∑ i = 1 min ⁡ { m , n } f ( σ i ( A − B ) ) , where σ i ( ⋅ ) denotes the i-th largest singular value of a matrix. This answers an open question that is of interest to both the compressive sensing and linear algebra communities. In particular, by taking f ( ⋅ ) = ( ⋅ ) p for any p ∈ ( 0 , 1 ] , we obtain a perturbation inequality for the so-called Schatten p-quasi-norm, which allows us to confirm the validity of a number of previously conjectured conditions for the recovery of low-rank matrices via the popular Schatten p-quasi-norm heuristic. We believe that our result will find further applications, especially in the study of low-rank matrix recovery.

This paper shows that the self-concordance parameter of the universal barrier on any n-dimensional proper convex domain is upper bounded by n. This bound is tight and improves the previous O(n) bound by Nesterov and Nemirovski. The key to our main result is a pair of new, sharp moment inequalities for s-concave distributions, which could be of independent interest.

The problem of phase retrieval is revisited and studied from a fresh perspective. In particular, we establish a connection between the phase retrieval problem and the sensor network localization problem, which allows us to utilize the vast theoretical and algorithmic literature on the latter to tackle the former. Leveraging this connection, we develop a two-stage algorithm for phase retrieval that can provably recover the desired signal. In both sparse and dense settings, our proposed algorithm improves upon prior approaches simultaneously in the number of required measurements for recovery and the reconstruction time. We present numerical results to corroborate our theory and to demonstrate the efficiency of the proposed algorithm. As a side result, we propose a new form of phase retrieval problem and connect it to the complex rigidity theory proposed by Gortler and Thurston (in: Connelly R, Ivic Weiss A, Whiteley W (eds) Rigidity and symmetry, Springer, New York, pp 131–154, 2014).

In this paper, we consider a simple and low-complexity discrete first-order method called the Generalized Power Method (GPM) for large-scale MIMO detection. The GPM is essentially a projected gradient method and exploits the fact that the projection onto the discrete MPSK or QAM constellation is efficiently computable. As our main contribution, we first show that under certain conditions on the channel and additive noise, the GPM will converge to the true symbol vector in a finite number of iterations. We then show that the aforementioned conditions will be satisfied with high probability under standard probabilistic models of the channel and noise. Besides enjoying strong theoretical guarantees, the proposed method is shown in our simulations to be competitive with existing methods in terms of both detection performance and numerical efficiency. We believe that our techniques will find further applications in the development of high-performance detection methods for massive MIMO.

In this work, we consider the robust beamforming design for secondary downlink multicasting channels, where primary users are present with norm-bounded channel errors. In particular, the max-min-fair formulation is considered and the resulting design problem is a quadratically constrained quadratic program (QCQP) with a set of semi-infinite constraints, which is NP-hard in general. As a remedy, we apply the semidefinite relaxation (SDR) technique and S-lemma to approximate the problem into a tractable form. The key contribution of this paper is to study the approximation quality. Our analytical results show that, the SDR solution achieves an objective value that is at least Ω(1/MN log J) times the optimal objective value, where M is the number of secondary users, J is the number of primary users, and N is the number of antennas at the secondary base station. This is a fundamentally new result for SDR applied to robust QCQPs. Practically, it provides a performance guarantee for the robust beamforming design. All these results are verified by our numerical simulations.

A fundamental problem arising in many areas of machine learning is the evaluation of the likelihood of a given observation under different nominal distributions. Frequently, these nominal distributions are themselves estimated from data, which makes them susceptible to estimation errors. We thus propose to replace each nominal distribution with an ambiguity set containing all distributions in its vicinity and to evaluate an \emph{optimistic likelihood}, that is, the maximum of the likelihood over all distributions in the ambiguity set. When the proximity of distributions is quantified by the Fisher-Rao distance or the Kullback-Leibler divergence, the emerging optimistic likelihoods can be computed efficiently using either geodesic or standard convex optimization techniques. We showcase the advantages of working with optimistic likelihoods on a classification problem using synthetic as well as empirical data.

The likelihood function is a fundamental component in Bayesian statistics. However, evaluating the likelihood of an observation is computationally intractable in many applications. In this paper, we propose a non-parametric approximation of the likelihood that identifies a probability measure which lies in the neighborhood of the nominal measure and that maximizes the probability of observing the given sample point. We show that when the neighborhood is constructed by the Kullback-Leibler divergence, by moment conditions or by the Wasserstein distance, then our \textit{optimistic likelihood} can be determined through the solution of a convex optimization problem, and it admits an analytical expression in particular cases. We also show that the posterior inference problem with our optimistic likelihood approximation enjoys strong theoretical performance guarantees, and it performs competitively in a probabilistic classification task.