Search

One objective of this paper is to propose a novel class of sequence pairs, called “quasi-orthogonal Z-complementary pairs (QOZCPs)”, each depicting Z-complementary property for their aperiodic auto-correlation sums and also having a low correlation zone when their aperiodic cross-correlation is considered. Construction of QOZCPs based on Successively Distributed Algorithms under Majorization Minimization (SDAMM) is presented. Another objective of this paper is to apply the proposed QOZCPs in fully polarimetric radar systems and analyse the corresponding ambiguity functions. It turns out that QOZCP waveforms are much more Doppler resilient than the known Golay complementary waveforms. [ABSTRACT FROM AUTHOR]

We consider a distributed stochastic optimization problem in networks with finite number of nodes. Each node adjusts its action to optimize the global utility of the network, which is defined as the sum of local utilities of all nodes. While Gradient descent method is a common technique to solve such optimization problem, the computation of the gradient may require much information exchange. In this paper, we consider that each node can only have a noisy numerical observation of its local utility, of which the closed-form expression is not available. This assumption is quite realistic, especially when the system is either too complex or constantly changing. Nodes may exchange partially the observation of their local utilities to estimate the global utility at each timeslot. We propose a distributed algorithm based on stochastic perturbation, under the assumption that each node has only part of the local utilities of the other nodes. We use stochastic approximation tools to prove that our algorithm converges almost surely to the optimum, given that the objective function is smooth and strictly concave. The convergence rate is also derived, under the additional assumption of strongly concave objective function. It is shown that the convergence rate scales as O (K−0.5) after a sufficient number of iterations K > K0, which is the optimal rate order in terms of K for our problem. Although the proposed algorithm can be applied to general optimization problems, we perform simulations for a typical power control problem in wireless networks and present numerical results to corroborate our claims. [ABSTRACT FROM AUTHOR]

The capacity of noisy quantum channels characterizes the highest rate at which information can be reliably transmitted and it is therefore of practical as well as fundamental importance. Capacities of classical channels are computed using alternating optimization schemes, called Blahut-Arimoto algorithms. In this work, we generalize classical Blahut-Arimoto algorithms to the quantum setting. In particular, we give efficient iterative schemes to compute the capacity of channels with classical input and quantum output, the quantum capacity of less noisy channels, the thermodynamic capacity of quantum channels, as well as the entanglement-assisted capacity of quantum channels. We give rigorous a priori and a posteriori bounds on the estimation error by employing quantum entropy inequalities and demonstrate fast convergence of our algorithms in numerical experiments. [ABSTRACT FROM AUTHOR]

Compressive phase retrieval refers to the problem of recovering a structured $n$ -dimensional complex-valued vector from its phase-less under-determined linear measurements. The non-linearity of the measurement process makes designing theoretically-analyzable efficient phase retrieval algorithms challenging. As a result, to a great extent, existing recovery algorithms only take advantage of simple structures such as sparsity and its convex generalizations. The goal of this article is to move beyond simple models through employing compression codes. Such codes are typically developed to take advantage of complex signal models to represent the signals as efficiently as possible. In this work, it is shown how an existing compression code can be treated as a black box and integrated into an efficient solution for phase retrieval. First, COmpressive PhasE Retrieval (COPER) optimization, a computationally-intensive compression-based phase retrieval method, is proposed. COPER provides a theoretical framework for studying compression-based phase retrieval. The number of measurements required by COPER is connected to $\kappa $ , the $\alpha $ -dimension (closely related to the rate-distortion dimension) of a given family of compression codes. To finds the solution of COPER, an efficient iterative algorithm called gradient descent for COPER (GD-COPER) is proposed. It is proven that under some mild conditions on the initialization and the compression code, if the number of measurements is larger than $ C \kappa ^{2} \log ^{2}~n$ , where $C$ is a constant, GD-COPER obtains an accurate estimate of the input vector in polynomial time. In the simulation results, JPEG2000 is integrated in GD-COPER to confirm the state-of-the-art performance of the resulting algorithm on real-world images. [ABSTRACT FROM AUTHOR]

We study the problem of maximizing the number of spanning trees in a connected graph with $n$ vertices and $m$ edges, by adding at most $k$ edges from a given set of $q$ candidate edges, a problem that has applications in many domains. We give both algorithmic and hardness results for this problem: 1) We give a greedy algorithm that obtains an approximation ratio of $(1 - 1/e - \epsilon)$ in the exponent of the number of spanning trees for any $\epsilon > 0$ in time $\widetilde {O}(m \epsilon ^{-1} + (n + q) \epsilon ^{-3})$ , where $\widetilde {O}(\cdot)$ hides ${\mathrm{ poly}}\log (n)$ factors. Our running time is optimal with respect to the input size, up to logarithmic factors, and improves on the $O(n^{3})$ running time of the previous proposed greedy algorithm with an approximation ratio $(1 - 1/e)$ in the exponent. Notably, the independence of our running time of $k$ is novel, compared to conventional top- $k$ selections on graphs that usually run in $\Omega (mk)$ time. 2) We show the exponential inapproximability of this problem by proving that there exists a constant $c > 0$ such that it is NP-hard to approximate the optimum number of spanning trees in the exponent within $(1 - c)$. [ABSTRACT FROM AUTHOR]

We study the properties of the Frank–Wolfe algorithm to solve the m-Exact-Sparse reconstruction problem, where a signal $y$ must be expressed as a sparse linear combination of a predefined set of atoms, called dictionary. We prove that when the signal is sparse enough with respect to the coherence of the dictionary, then the iterative process implemented by the Frank–Wolfe algorithm only recruits atoms from the support of the signal, is the smallest set of atoms from the dictionary that allows for a perfect reconstruction of $y$. We also prove that under this same condition, there exists an iteration beyond which the algorithm converges exponentially. [ABSTRACT FROM AUTHOR]

Factor graphs are important models for succinctly representing probability distributions in machine learning, coding theory, and statistical physics. Several computational problems, such as computing marginals and partition functions, arise naturally when working with factor graphs. Belief propagation is a widely deployed iterative method for solving these problems. However, despite its significant empirical success, several questions regarding the correctness and efficiency of belief propagation remain open. The Bethe approximation is an optimization-based method for approximating the partition functions. While it is known that the stationary points of the Bethe approximation coincide with the fixed points of belief propagation, in general, the relation between the Bethe approximation and the partition function is not well understood. It has been observed that for a few classes of factor graphs, the Bethe approximation gives a lower bound to the partition function, which distinguishes them from the general case, where neither a lower bound nor an upper bound holds universally. This has been rigorously proved for permanents and for attractive graphical models. Here, we consider bipartite factor graphs over binary alphabet and show that if the local constraints satisfy a certain analytic property, the Bethe approximation is a lower bound to the partition function, generalizing an analogous inequality between the permanent and the Bethe permanent of a matrix with non-negative entries. We arrive at this result by viewing the factor graphs through the lens of polynomials, which allows us to reformulate the Bethe approximation as an optimization problem involving polynomials. The sufficient condition for our lower bound property to hold is inspired by the recent developments in the theory of real stable polynomials. We believe that this way of viewing factor graphs and its connection to real stability might lead to a better understanding of belief propagation and factor graphs in general. [ABSTRACT FROM AUTHOR]

We consider an $\ell _{2}$ -regularized non-convex optimization problem for recovering signals from their noisy phaseless observations. We design and study the performance of a message passing algorithm that aims to solve this optimization problem. We consider the asymptotic setting $m,n \rightarrow \infty $ , $m/n \rightarrow \delta $ and obtain sharp performance bounds, where $m$ is the number of measurements and $n$ is the signal dimension. We show that for complex signals, the algorithm can perform accurate recovery with only $m = (({64}/{\pi ^{2}})-4)n \approx 2.5n$ measurements. Also, we provide a sharp analysis on the sensitivity of the algorithm to noise. We highlight the following facts about our message passing algorithm: 1) adding $\ell _{2}$ regularization to the non-convex loss function can be beneficial and 2) spectral initialization has a marginal impact on the performance of the algorithm. The sharp analyses, in this paper, not only enable us to compare the performance of our method with other phase recovery schemes but also shed light on designing better iterative algorithms for other non-convex optimization problems. [ABSTRACT FROM AUTHOR]

We study the convergence of the iterative projected gradient (IPG) algorithm for arbitrary (possibly non-convex) sets when both the gradient and projection oracles are computed approximately. We consider different notions of approximation of which we show that the progressive fixed precision and the $(1+ \varepsilon)$ -optimal oracles can achieve the same accuracy as for the exact IPG algorithm. We show that the former scheme is also able to maintain the (linear) rate of convergence of the exact algorithm under the same embedding assumption. In contrast, the $(1+ \varepsilon)$ -approximate oracle requires a stronger embedding condition, moderate compression ratios and it typically slows down the convergence. We apply our results to accelerate solving a class of data driven compressed sensing problems, where we replace iterative exhaustive searches over large data sets by fast approximate nearest neighbor search strategies based on the cover tree data structure. For data sets with low intrinsic dimensions, our proposed algorithm achieves a complexity logarithmic in terms of the data set population as opposed to the linear complexity of a brute force search. By running several numerical experiments, we conclude similar observations as predicted by our theoretical analysis. [ABSTRACT FROM AUTHOR]

We consider a generalized version of the correlation clustering problem, defined as follows. Given a complete graph $G$ whose edges are labeled with + or −, we wish to partition the graph into clusters while trying to avoid errors: + edges between clusters or − edges within clusters. Classically, one seeks to minimize the total number of such errors. We introduce a new framework that allows the objective to be a more general function of the number of errors at each vertex (for example, we may wish to minimize the number of errors at the worst vertex) and provides a rounding algorithm which converts “fractional clusterings” into discrete clusterings while causing only a constant-factor blowup in the number of errors at each vertex. This rounding algorithm yields constant-factor approximation algorithms for the discrete problem under a wide variety of objective functions. [ABSTRACT FROM PUBLISHER]

In many application areas ranging from bioinformatics to imaging, we are faced with the following question: can we recover a sparse vector xo \in \mathbb {R}^{N} from its undersampled set of noisy observations y \in \mathbb R^n , y= A xo+ w . The last decade has witnessed a surge of algorithms and theoretical results to address this question. One of the most popular schemes is the \ell p -regularized least squares given by the following formulation: \hat x(\gamma ,p ) \in \arg \min x~({1}/{2})\| {y - Ax} \|2^{2} + \gamma {\| x \|p^{p}} , where p \in [0, 1] . Among these optimization problems, the case p = 1 , also known as LASSO, is the best accepted in practice, for the following two reasons. First, thanks to the extensive studies performed in the fields of high-dimensional statistics and compressed sensing, we have a clear picture of LASSO’s performance. Second, it is convex and efficient algorithms exist for finding its global minima. Unfortunately, neither of the above two properties hold for 0 \leq p<1 . However, they are still appealing because of the following folklores in the high-dimensional statistics. First, \hat x(\gamma , p ) is closer to than \hat {x}(\gamma ,1) . Second, if we employ iterative methods that aim to converge to a local minima of {\arg \min }_{x}~({1}/{2})\| {y - Ax} \|_{2}^{2} + \gamma {\| x \|_{p}^{p}} , then under good initialization, these algorithms converge to a solution that is still closer to xo than \hat {x}(\gamma ,1) . In spite of the existence of plenty of empirical results that support these folklore theorems, the theoretical progress to establish them has been very limited. This paper aims to study the above-mentioned folklore theorems and establish their scope of validity. Starting with approximate message passing (AMP) algorithm as a heuristic method for solving \ell p -regularized least squares, we study the following questions. First, what is the impact of initialization on the performance of the algorithm? Second, when does the algorithm recover the sparse signal xo under a “good” initialization? Third, when does the algorithm converge to the sparse signal regardless of the initialization? Studying these questions will not only shed light on the second folklore theorem, but also lead us to the answer the first one, i.e., the performance of the global optima \hat x(\gamma , p ) . For that purpose, we employ the replica analysis1 to show the connection between the solution of AMP and \hat {x}(\gamma , p) in the asymptotic settings. This enables us to compare the accuracy of \hat x(\gamma ,p )$ and $\hat x(\gamma ,1 )$ . In particular, we will present an accurate characterization of the phase transition and noise sensitivity of \ell p -regularized least squares for every $0 \leq p \leq 1$ . Our results in the noiseless setting confirm that \ell p -regularized least squares (if $\gamma $ is tuned optimally) exhibits the same phase transition for every $0 \leq p< 1$ and this phase transition is much better than that of LASSO. Furthermore, we show that in the noisy setting, there is a major difference between the performance of \ell p -regularized least squares with different values of $p$ . For instance, we will show that for very small and very large measurement noises, $p = 0$ and $p = 1$ outperform the other values of $p$ , respectively.1

Replica method is a widely accepted heuristic in statistical physics for analyzing large disordered systems.

Impulsive noise features in many modern communication systems—ranging from wireless to molecular—and is often modeled by the $\alpha $ -stable distribution. At present, the capacity of $\alpha $ -stable noise channels is not well understood, with the exception of Cauchy noise ( $\alpha = 1$ ) with a logarithmic constraint and Gaussian noise ( $\alpha = 2$ ) with a power constraint. In this paper, we consider additive symmetric $\alpha $ -stable noise channels with $\alpha \in (1,2]$ . We derive bounds for the capacity with an absolute moment constraint. We then compare our bounds with a numerical approximation via the Blahut–Arimoto algorithm, which provides insight into the effect of noise parameters on the bounds. In particular, we find that our lower bound is in good agreement with the numerical approximation for $\alpha $ near 2. [ABSTRACT FROM AUTHOR]

We consider the problem of recovering a complete (i.e., square and invertible) matrix A0 , from Y \in \mathbb R ^n \times p with Y = \boldsymbol A0 X0 , provided X0 is sufficiently sparse. This recovery problem is central to theoretical understanding of dictionary learning, which seeks a sparse representation for a collection of input signals and finds numerous applications in modern signal processing and machine learning. We give the first efficient algorithm that provably recovers A0 when X0 has O \left ( n \right ) nonzeros per column, under suitable probability model for X0 . Our algorithmic pipeline centers around solving a certain nonconvex optimization problem with a spherical constraint, and hence is naturally phrased in the language of manifold optimization. In a companion paper, we have showed that with high probability, our nonconvex formulation has no “spurious” local minimizers and around any saddle point, the objective function has a negative directional curvature. In this paper, we take advantage of the particular geometric structure and describe a Riemannian trust region algorithm that provably converges to a local minimizer with from arbitrary initializations. Such minimizers give excellent approximations to the rows of X0 . The rows are then recovered by a linear programming rounding and deflation. [ABSTRACT FROM AUTHOR]

Generalized linear models, where a random vector x is observed through a noisy, possibly nonlinear, function of a linear transform \mathrm z= \mathrm A \mathrm x , arise in a range of applications in nonlinear filtering and regression. Approximate message passing (AMP) methods, based on loopy belief propagation, are a promising class of approaches for approximate inference in these models. AMP methods are computationally simple, general, and admit precise analyses with testable conditions for optimality for large i.i.d. transforms A. However, the algorithms can diverge for general A. This paper presents a convergent approach to the generalized AMP (GAMP) algorithm based on direct minimization of a large-system limit approximation of the Bethe free energy (LSL-BFE). The proposed method uses a double-loop procedure, where the outer loop successively linearizes the LSL-BFE and the inner loop minimizes the linearized LSL-BFE using the alternating direction method of multipliers (ADMM). The proposed method, called ADMM-GAMP, is similar in structure to the original GAMP method, but with an additional least-squares minimization. It is shown that for strictly convex, smooth penalties, ADMM-GAMP is guaranteed to converge to a local minimum of the LSL-BFE, thus providing a convergent alternative to GAMP that is stable under arbitrary transforms. Simulations are also presented that demonstrate the robustness of the method for non-convex penalties as well. [ABSTRACT FROM PUBLISHER]

The estimation of a random vector with independent components passed through a linear transform followed by a componentwise (possibly nonlinear) output map arises in a range of applications. Approximate message passing (AMP) methods, based on Gaussian approximations of loopy belief propagation, have recently attracted considerable attention for such problems. For large random transforms, these methods exhibit fast convergence and admit precise analytic characterizations with testable conditions for optimality, even for certain non-convex problem instances. However, the behavior of AMP under general transforms is not fully understood. In this paper, we consider the generalized AMP (GAMP) algorithm and relate the method to more common optimization techniques. This analysis enables a precise characterization of the GAMP algorithm fixed points that applies to arbitrary transforms. In particular, we show that the fixed points of the so-called max-sum GAMP algorithm for MAP estimation are critical points of a constrained maximization of the posterior density. The fixed points of the sum-product GAMP algorithm for estimation of the posterior marginals can be interpreted as critical points of a certain free energy. [ABSTRACT FROM PUBLISHER]

We point out an issue with one of the results in Bellala et al. [1] that invokes a main result on adaptive stochastic minimum cost cover problem (Theorem 5.8) of Golovin and Krause. We construct an example that shows that the proof of Theorem 5.8 of Golovin and Krause is invalid, and therefore, the proof in Bellala et al. about the near-optimum performance of their algorithm is also invalid. [ABSTRACT FROM PUBLISHER]

We propose an iterative method for approximately computing the capacity of discrete memoryless channels, possibly under additional constraints on the input distribution. Based on duality of convex programming, we derive explicit upper and lower bounds for the capacity. The presented method requires O(M^2 N \sqrt \log N/\varepsilon ) to provide an estimate of the capacity to within $\varepsilon $ , where $N$ and $M$ denote the input and output alphabet size; a single iteration has a complexity $O(M N)$ . We also show how to approximately compute the capacity of memoryless channels having a bounded continuous input alphabet and a countable output alphabet under some mild assumptions on the decay rate of the channel’s tail. It is shown that discrete-time Poisson channels fall into this problem class. As an example, we compute sharp upper and lower bounds for the capacity of a discrete-time Poisson channel with a peak-power input constraint. [ABSTRACT FROM AUTHOR]

Random projection has been widely used in data classification. It maps high-dimensional data into a low-dimensional subspace in order to reduce the computational cost in solving the related optimization problem. While previous studies are focused on analyzing the classification performance in the low-dimensional space, in this paper, we consider the recovery problem, i.e., how to accurately recover the optimal solution to the original high-dimensional optimization problem based on the solution learned after random projection. We present a simple algorithm, termed dual random projection, which uses the dual solution of the low-dimensional optimization problem to recover the optimal solution to the original problem. Our theoretical analysis shows that with a high probability, the proposed algorithm is able to accurately recover the optimal solution to the original problem, provided that the data matrix is (approximately) low-rank and/or optimal solution is (approximately) sparse. We further show that the proposed algorithm can be applied iteratively to reducing the recovery error exponentially. [ABSTRACT FROM PUBLISHER]

In this paper, a low-complexity delay-aware cross-layer scheduling algorithm for two-hop relay communication systems is proposed. The complex interactions of the queues at the source node and the M relay nodes (RSs) are modeled as an infinite horizon average reward Markov decision process (MDP), whose state space involves the joint queue state information (QSI) of the queues at the source node and the M RSs as well as the joint channel state information (CSI) of all S-R and R-D links. To address the curse of dimensionality, an equivalent MDP formulation is first proposed, where the system state depends only on global QSI. Furthermore, using approximate MDP and stochastic learning, an auction-based distributed online learning algorithm is derived, where each node iteratively estimates a per-node value function based on real-time observations of the local CSI and local QSI as well as signaling between relays. The combined distributed learning converges almost surely to a global optimal solution for large arrivals. Finally, it is showed by simulations that the proposed scheme achieves significant gain compared with various baselines such as the conventional CSIT-only control and the throughput optimal control (in stability sense). [ABSTRACT FROM AUTHOR]

In this paper, a distributed stochastic approximation algorithm is studied. Applications of such algorithms include decentralized estimation, optimization, control or computing. The algorithm consists in two steps: a local step, where each node in a network updates a local estimate using a stochastic approximation algorithm with decreasing step size, and a gossip step, where a node computes a local weighted average between its estimates and those of its neighbors. Convergence of the estimates toward a consensus is established under weak assumptions. The approach relies on two main ingredients: the existence of a Lyapunov function for the mean field in the agreement subspace, and a contraction property of the random matrices of weights in the subspace orthogonal to the agreement subspace. A second-order analysis of the algorithm is also performed under the form of a central limit Theorem. The Polyak-averaged version of the algorithm is also considered. [ABSTRACT FROM AUTHOR]