Search

The problem of range estimation based on noisy measurements with phase ambiguity can be solved using signals across multiple frequencies by existing algorithms based on either the Chinese Remainder Theorem or lattice theory. The performances of these algorithms are constrained by the trade-off between SNR of measurements and required estimation accuracy. In this paper, we firstly propose an algorithm to find a set of wavelengths satisfying the conditions to apply the closed-form lattice algorithm from a given interval. Then we propose an enhanced lattice algorithm for range estimation based on existing lattice approaches. In the conventional lattice algorithm, the selection of an integer vector by the estimator often fails to be the ground truth because of noise. As a result, the true value can be a neighbouring lattice point of the estimated point where neighbours are defined in terms of a distance depending on the noise characteristics. In this paper, all neighbouring lattice points of the estimated point obtained by a conventional lattice algorithm are regarded as candidates for the new estimate. Then an efficient estimator is presented to choose one of those candidates to be the new estimate. The performance of the proposed algorithm, i.e. the successful probability of reconstruction, is derived mathematically. Additionally, a computation-reduced algorithm is presented to reduce the overhead of computation. The calculated probability and simulation results demonstrate the efficiency of the proposed algorithm. [ABSTRACT FROM AUTHOR]

The Unlimited Sensing Framework (USF) was recently introduced to overcome the sensor saturation bottleneck in conventional digital acquisition systems. At its core, the USF converts a continuous-time high-dynamic-range (HDR) signal into folded, low-dynamic-range, modulo samples and allows the recovery of the HDR signal via algorithmic unfolding. In hardware, however, implementing ideal modulo folding requires careful calibration, analog design and high precision. At the interface of theory and practice, this paper explores a computational sampling strategy that relaxes strict hardware requirements via a novel, mathematically guaranteed reconstruction. We start with a generalized model for USF with two new parameters modeling hysteresis and folding transients in addition to the modulo threshold. Hysteresis accounts for mismatches between the reset threshold and the amplitude displacement at the folding time and the folding transient is a continuous transition period in the implementation of a reset. Both these effects are motivated by our hardware experiments and also occur in previous, domain-specific applications. We show that hysteresis is beneficial for USF and leverage it to derive the first recovery guarantees in the context of our generalized USF model for a certain sampling rate regime. Additionally, we show how the sampling rate requirement can be greatly reduced via a direct generalization of the proposed recovery. Our theoretical work is corroborated by hardware experiments with a hysteresis enabled, modulo ADC testbed comprising off-the-shelf electronic components. Thus, by capitalizing on a collaboration between hardware and algorithms, our paper enables an end-to-end pipeline for HDR sampling allowing more flexible hardware implementations. [ABSTRACT FROM AUTHOR]

In this paper, we propose to extend the standard Convolutional Dictionary Learning problem to a tensor representation where the activations are constrained to be “low-rank” through a Canonical Polyadic decomposition. We show that this additional constraint increases the robustness of the CDL with respect to noise and improve the interpretability of the final results. In addition, we discuss in detail the advantages of this representation and introduce two algorithms, based on ADMM or FISTA, that efficiently solve this problem. We show that by exploiting the low rank property of activations, they achieve lower complexity than the main CDL algorithms. Finally, we evaluate our approach on a wide range of experiments, highlighting the modularity and the advantages of this tensorial low-rank formulation. [ABSTRACT FROM AUTHOR]

This paper studies the convergence properties of the well-known message-passing algorithm for convex optimisation. Under the assumption of pairwise separability and scaled diagonal dominance, asymptotic convergence is established and a simple bound for the convergence rate is provided for message-passing. In comparison with previous results, our results do not require the given convex program to have known convex pairwise components and that our bound for the convergence rate is tighter and simpler. When specialised to quadratic optimisation, we generalise known results by providing a very simple bound for the convergence rate. [ABSTRACT FROM AUTHOR]

This paper proposes an efficient algorithm for robust sensor placement with the purpose of recovering a source signal from noisy measurements. To model uncertainty on the spatially-variant sensors gain and on the spatially correlated noise, we assume that both are realizations of Gaussian processes. Since the signal to noise ratio (SNR) is also uncertain in this context, to achieve a robust signal extraction, we propose a new placement criterion based on the maximization of the probability that the SNR exceeds a given threshold. This criterion can be easily evaluated using the Gaussian process assumption. Moreover, to reduce the computational complexity of the joint maximization of the criterion with respect to all sensor positions, we suggest a sequential maximization approach, where the sensor positions are chosen one at a time. Finally, we present numerical results showing the superior robustness of the proposed approach when compared to standard sensor placement criteria aimed at interpolating the spatial gain and to a recently proposed criterion aimed at maximizing the average SNR. [ABSTRACT FROM AUTHOR]

We consider the problem of minimizing the $\ell _1$ norm of a linear map over the sphere, which arises in various machine learning applications such as orthogonal dictionary learning (ODL) and robust subspace recovery (RSR). The problem is numerically challenging due to its nonsmooth objective and nonconvex constraint, and its algorithmic aspects have not been well explored. In this paper, we show how the manifold structure of the sphere can be exploited to design fast algorithms with provable guarantees for tackling this problem. Specifically, our contribution is fourfold. First, we present a manifold proximal point algorithm (ManPPA) for the problem and show that it converges at a global sublinear rate. Furthermore, we show that ManPPA can achieve a local quadratic convergence rate when applied to sharp instances of the problem. Second, we develop a semismooth Newton-based inexact augmented Lagrangian method for computing the search direction in each iteration of ManPPA and show that it has an asymptotic superlinear convergence rate. Third, we propose a stochastic variant of ManPPA called StManPPA, which is well suited for large-scale computation, and establish its sublinear convergence rate. Both ManPPA and StManPPA have provably faster convergence rates than existing subgradient-type methods. Fourth, using ManPPA as a building block, we propose a new heuristic method for solving a matrix analog of the problem, in which the sphere is replaced by the Stiefel manifold. The results from our extensive numerical experiments on the ODL and RSR problems demonstrate the efficiency and efficacy of our proposed methods. [ABSTRACT FROM AUTHOR]

Due to the advantage of capacity-achieving, polar codes have been extended to the block fading channel whereas most constructions involve complex iterative-calculation. In this paper, we establish a systematic framework to analyze the error performance of polar codes in the case of block mapping and random mapping. For both the mappings, by introducing the new concept, named split polar spectrum, we derive the upper bound on the error probability of polarized channel which explicitly reveals the relationship between the diversity order $L$ and the block-wise weight distribution of the codeword. For the special case $L=2$ in the block mapping, we design the enumeration algorithm to calculate the exact split polar spectrum based on the general MacWilliams identities. For arbitrary diversity order in the random mapping, with the help of uniform interleaving, we derive the approximate split polar spectrum by combining the polar spectrum and the probability of fading pattern for a specific weight. Furthermore, we propose the design criteria to construct polar codes over the block fading channel. The full diversity criterion is the primary target to achieve the diversity gain and the product distance criterion requires to maximize the product of the block-wise Hamming distance whereby obtain the coding gain. Guided by these design criteria, the construction metrics, respectively named polarized diversity weight (PDW) and simplified PDW (SPDW) are proposed to designpolar codes in both mappings. Such simple metrics can construct polar codes with similar or better performance over those based on traditional methods in block fading channel. [ABSTRACT FROM AUTHOR]

We correct errors in step 6 of Algorithm 1 given in the paper ‘'Sparse-Group Lasso for Graph Learning from Multi-Attribute Data.’' Other parts of the paper including numerical results are unchanged as the algorithm was implemented correctly. [ABSTRACT FROM AUTHOR]

This paper considers stochastic convex optimization problems with two sets of constraints: (a) deterministic constraints on the domain of the optimization variable, which are difficult to project onto; and (b) deterministic or stochastic constraints that admit efficient projection. Problems of this form arise frequently in the context of semidefinite programming as well as when various NP-hard problems are solved approximately via semidefinite relaxation. Since projection onto the first set of constraints is difficult, it becomes necessary to explore projection-free algorithms, such as the stochastic Frank-Wolfe (FW) algorithm. On the other hand, the second set of constraints cannot be handled in the same way, and must be incorporated as an indicator function within the objective function, thereby complicating the application of FW methods. Similar problems have been studied before; however, they suffer from slow convergence rates. This work, equipped with momentum based gradient tracking technique, guarantees fast convergence rates on par with the best-known rates for problems without the second set of constraints. Zeroth-order variants of the proposed algorithms are also developed and again improve upon the state-of-the-art rate results. We further propose the novel trimmed FW variants that enjoy the same convergence rates as their classical counterparts, but are empirically shown to require significantly fewer calls to the linear minimization oracle speeding up the overall algorithm. The efficacy of the proposed algorithms is tested on relevant applications of sparse matrix estimation, clustering via semidefinite relaxation, and uniform sparsest cut problem. [ABSTRACT FROM AUTHOR]

In this paper, we design and analyze Mc2g (Matrix Completion with 2 Graphs), an efficient algorithm that performs matrix completion in the presence of social and item similarity graphs. Mc2g runs in quasilinear time and is parameter free. It is based on spectral clustering and local refinement steps. For the matrix completion problem which possesses additional block structures in its rows and columns, we derive the expected number of sampled entries required for Mc2g to succeed, and further show that it matches an information-theoretic lower bound up to a constant factor for a wide range of parameters. We perform extensive experiments on both synthetic datasets and a semi-real dataset inspired by real graphs. The experimental results show that Mc2g outperforms other state-of-the-art matrix completion algorithms. [ABSTRACT FROM AUTHOR]

The use of a large-scale antenna array (LSAA) has become an important characteristic of multi-antenna communication systems to achieve beamforming gains such as in designing millimeter-wave (mmWave) systems to combat severe propagation losses. In such applications, each antenna element has to be driven by a radio frequency (RF) chain for the implementation of fully-digital beamformers, significantly increasing the hardware cost, complexity, and power consumption. Therefore, constant-modulus analog beamforming (CMAB) becomes a viable solution. In this paper, we consider the scaled analog beamforming (SAB) or constant-modulus analog beamforming (CMAB) architecture and design the system parameters by solving two variants of beampattern matching problem. In the first case, both the magnitude and phase of the beampattern are matched to the given desired beampattern whereas in the second case, only the magnitude of the beampattern is matched. Both the beampattern matching problems are cast as a variant of the constant-modulus least-squares (CLS) problem. We provide efficient algorithms based on the alternating majorization-minimization (AMM) framework that combines the alternating minimization and the MM frameworks and the conventional-cyclic coordinate descent (C-CCD) algorithms to solve the problem in each case. We also propose algorithms based on a new modified-CCD (M-CCD) based approach. For all the developed algorithms we prove convergence to a Karush-Kuhn-Tucker (KKT) point (or a stationary point). Numerical results demonstrate that the proposed algorithms converge faster than the state-of-the-art solutions. Among all the algorithms, the M-CCD-based algorithms have faster convergence when evaluated in terms of the number of iterations and the AMM-based algorithms offer lower complexity. [ABSTRACT FROM AUTHOR]

While many distributed optimization algorithms have been proposed for solving smooth or convex problems over the networks, few of them can handle non-convex and non-smooth problems. Based on a proximal primal-dual approach, this paper presents a new (stochastic) distributed algorithm with Nesterov momentum for accelerated optimization of non-convex and non-smooth problems. Theoretically, we show that the proposed algorithm can achieve an $\epsilon$ -stationary solution under a constant step size with $\mathcal {O}(1/\epsilon ^2)$ computation complexity and $\mathcal {O}(1/\epsilon)$ communication complexity when the epigraph of the non-smooth term is a polyhedral set. When compared to the existing gradient tracking based methods, the proposed algorithm has the same order of computation complexity but lower order of communication complexity. To the best of our knowledge, the presented result is the first stochastic algorithm with the $\mathcal {O}(1/\epsilon)$ communication complexity for non-convex and non-smooth problems. Numerical experiments for a distributed non-convex regression problem and a deep neural network based classification problem are presented to illustrate the effectiveness of the proposed algorithms. [ABSTRACT FROM AUTHOR]

In this paper, we propose a novel adaptive importance sampling (AIS) algorithm for probabilistic inference. The sampler learns a proposal distribution adaptation strategy by framing AIS as a reinforcement learning problem. Under this structure, the proposal distribution of the sampler is treated as an agent whose state is controlled using a parameterized policy. At each iteration of the algorithm, the agent earns a reward that is related to its contribution to the variance of the AIS estimator of the normalization constant of the target distribution. Policy gradient methods are employed to learn a locally optimal policy that maximizes the expected value of the sum of all rewards. Numerical simulations on two different examples demonstrate promising results for the future application of the proposed method to complex Bayesian models. [ABSTRACT FROM AUTHOR]

In this paper, we consider the policy evaluation problem in reinforcement learning with agents on a decentralized and directed network. In order to evaluate the quality of a fixed policy in this decentralized setting, one option is for agents to run decentralized temporal-difference (TD) collaboratively. To account for the practical scenarios where the state and action spaces are large and malicious attacks emerge, we focus on the decentralized TD learning with linear function approximation in the presence of malicious agents (often termed as Byzantine agents). We propose a trimmed mean-based Byzantine-resilient decentralized TD algorithm to perform policy evaluation in this setting. We establish the finite-time convergence rate, as well as the asymptotic learning error that depends on the number of Byzantine agents. Numerical experiments corroborate the robustness of the proposed algorithm. [ABSTRACT FROM AUTHOR]

This paper presents algorithms for the parallelization of inference in hidden Markov models (HMMs). In particular, we propose a parallel forward-backward type of filtering and smoothing algorithm as well as a parallel Viterbi-type maximum-a-posteriori (MAP) algorithm. We define associative elements and operators to pose these inference problems as all-prefix-sums computations and parallelize them using the parallel-scan algorithm. The advantage of the proposed algorithms is that they are computationally efficient in HMM inference problems with long time horizons. We empirically compare the performance of the proposed methods to classical methods on a highly parallel graphics processing unit (GPU). [ABSTRACT FROM AUTHOR]

In this paper, we extend the bilinear generalized approximate message passing (BiG-AMP) approach, originally proposed for high-dimensional generalized bilinear regression, to the multi-layer case for the handling of cascaded problem such as matrix-factorization problem arising in relay communication among others. Assuming statistically independent matrix entries with known priors, the new algorithm called ML-BiGAMP could approximate the general sum-product loopy belief propagation (LBP) in the high-dimensional limit enjoying a substantial reduction in computational complexity. We demonstrate that, in large system limit, the asymptotic MSE performance of ML-BiGAMP could be fully characterized via a set of simple one-dimensional equations termed state evolution (SE). We establish that the asymptotic MSE predicted by ML-BiGAMP’ SE matches perfectly the exact MMSE predicted by the replica method, which is well-known to be Bayes-optimal but infeasible in practice. This consistency indicates that the ML-BiGAMP may still retain the same Bayes-optimal performance as the MMSE estimator in high-dimensional applications, although ML-BiGAMP's computational burden is far lower. As an illustrative example of the general ML-BiGAMP, we provide a detector design that could estimate the channel fading and the data symbols jointly with high precision for the two-hop amplify-and-forward relay communication systems. [ABSTRACT FROM AUTHOR]

In this paper, we investigate designs of linear precoders for vector Gaussian channels via stochastic optimizations and deep neural networks (DNNs). We assume that the channel inputs are drawn from practical finite alphabets, and we search for precoders maximizing the mutual information between channel inputs and outputs. Though the problem is generally non-convex, we prove that when the right singular matrix of precoder is fixed, any local optima of this problem is a global optima. Based on this fact, an efficient projected stochastic gradient descent (PSGD) algorithm is designed to search the optimal precoders. Moreover, to reduce the complexity of calculating a posterior means involved in gradients calculation, K-best algorithm is adopted to make approximations of a posterior means with negligible loss of accuracy. Furthermore, to avoid explicit calculation of mutual information and its gradients, DNN-based autoencoders (AEs) are constructed for this precoding task, and an efficient training algorithm is proposed. We also prove that the AEs, with ‘softmax’ activation function and ‘categorical cross entropy’ loss, maximize the mutual information under reasonable assumptions. Then, in order to extend the AE methods to large scale systems, ‘sigmoid’ activation function and ‘binary cross entropy’ loss are used such that the size of AEs will not grow prohibitively large. We prove that this maximizes a lower bound of the mutual information under reasonable assumptions. Finally, to make the precoders practical for high speed wireless scenarios, we propose an offline training paradigm which trains DNNs to infer optimal precoders given channel state information instead of training online for every different channel. Simulation results show that all the proposed methods work well in maximizing mutual information and improving bit error rate (BER) performance. [ABSTRACT FROM AUTHOR]

Direction of arrival (DOA) estimation is a classical topic in source localization. Notably, a reliable grid-free sparse representation algorithm, called FRI (finite rate of innovation) algorithm, was proposed to recover the finite number of Dirac pulses from a stream of 1D temporal samples, which also offers a efficient solution to the DOA estimation problem. Typically, FRI method assumes uniform sampling with single snapshot. However, the actual situation is richer and more diverse. Motivated by the requests of practical applications (e.g. array deployment, algorithm run-speed, etc.), a generic FRI method is proposed to tackle the more general case in practice, i.e. non-uniform sampling with multiple snapshots. Instead of annihilating the measured sensor data, a model-fitting method is used to robustly retrieve the sparse representation (i.e. DOAs and associated amplitudes) of the 1D samples. We demonstrate that our algorithm can handle challenging DOA tasks with high-resolution, which we validate in various conditions, such as multiple coherent sources, insufficient signal snapshots, low signal-to-noise ratio (SNR), etc. Moreover, we show that the computational complexity of our algorithm mainly scales with the number of sources and varies very slowly with the number of samples and snapshots, which meets the needs of a wider range of practical applications. [ABSTRACT FROM AUTHOR]

We design an efficient robust multi-group multicast beamforming scheme for massive multiple-input multiple-output (MIMO) systems. Assuming only estimates of the channel covariance matrices are available at the base station with a bounded error, we formulate the robust quality-of-service (QoS) problem, which is to minimize the transmit power subject to the worst-case minimum signal-to-interference-plus-noise-ratio (SINR) guarantee. We directly solve the worst-case SINR problem and convert the robust QoS constraint into a number of non-convex constraints. Based on the recent convergence result of the alternating direction method of multipliers (ADMM) for non-convex problems, we develop an ADMM-based fast algorithm to directly tackle the reformulated non-convex problem with a convergence guarantee. The algorithm contains two layers of ADMM procedures. We design the outer-layer ADMM to decompose the problem into three convex subproblems and solve them alternatingly. We further develop an inner-layer consensus-ADMM-based algorithm to efficiently solve one subproblem. By exploring each subproblem structure and developing the special optimization techniques, we obtain closed-form or semi-closed-form solutions to each subproblem. These results lead to a fast iterative algorithm, which is guaranteed to converge to a stationary point of the original robust QoS problem. Simulation shows that our proposed algorithm provides a favorable performance compared with existing alternative methods with magnitudes of computational complexity reduction. [ABSTRACT FROM AUTHOR]

In this work, we apply deep learning to estimate the direction-of-arrival (DoA) of multiple narrowband signals with a uniform linear array in a coherent environment. First, the logarithmic eigenvalue-based classification network (LogECNet) is introduced to enhance signal number detection accuracy in challenging scenarios, such as the low signal-to-noise (SNR) regime and limited snapshots. Next, a multi-label classification model called the root-spectrum network (RSNet) is devised to estimate the DoAs using the signal number inferred by LogECNet. In the proposed architecture, the full-row Toeplitz matrices reconstruction (FTMR), which exploits all rows of the signal covariance matrix (SCM), is combined with LogECNet and RSNet to inversely map the SCM to the numerical DoAs in the coherent scenario. It is shown that the eigenvalues factorized from the FTMR output matrix become more robust sources for signal enumeration than those of the forward/backward spatial smoothing (FBSS) algorithm. Furthermore, the logarithmic scaling of the eigenvalues of the FTMR results in LogECNet outperforming other detectors. The simulation results show our proposed method not only improves the signal number detection and angular estimation performance, but also achieves the complexity reduction with respect to the prior schemes. [ABSTRACT FROM AUTHOR]

We consider the sparse phase retrieval problem of recovering a sparse signal $\mathbf {x}$ in $\mathbb {R}^d$ from intensity-only measurements in dimension $d \geq 2$. Sparse phase retrieval can often be equivalently formulated as the problem of recovering a signal from its autocorrelation, which is in turn directly related to the combinatorial problem of recovering a set from its pairwise differences. In one spatial dimension, this problem is well studied and known as the turnpike problem. In this work, we present MISTR (Multidimensional Intersection Sparse supporT Recovery), an algorithm which exploits this formulation to recover the support of a multidimensional signal from magnitude-only measurements. MISTR takes advantage of the structure of multiple dimensions to provably achieve the same accuracy as the best one-dimensional algorithms in dramatically less time. We prove theoretically that MISTR correctly recovers the support of signals distributed as a Gaussian point process with high probability as long as sparsity is at most $\mathcal {O}(n^{d\theta })$ for any $\theta < 1/2$ , where $n^d$ represents pixel size in a fixed image window. In the case that magnitude measurements are corrupted by noise, we provide a thresholding scheme with theoretical guarantees for sparsity at most $\mathcal {O}(n^{d\theta })$ for $\theta < 1/4$ that obviates the need for MISTR to explicitly handle noisy autocorrelation data. Detailed and reproducible numerical experiments demonstrate the effectiveness of our algorithm, showing that in practice MISTR enjoys time complexity which is nearly linear in the size of the input. [ABSTRACT FROM AUTHOR]

We consider stochastic optimization of a smooth non-convex loss function with a convex non-smooth regularizer. In the online setting, where a single sample of the stochastic gradient of the loss is available at every iteration, the problem can be solved using the proximal stochastic gradient descent (SGD) algorithm and its variants. However in many problems, especially those arising in communications and signal processing, information beyond the stochastic gradient may be available thanks to the structure of the loss function. By constructing a strongly convex surrogate of the loss function at every iteration, the stochastic SCA algorithms can exploit the structural properties of the loss function. In this work, we take a closer look at the stochastic SCA algorithm and develop its asynchronous variant which can be used for resource allocation in wireless networks. While the stochastic SCA algorithm is known to converge asymptotically, its iteration complexity has not been well-studied, and is the focus of the current work. The insights obtained from the non-asymptotic analysis allow us to develop a more practical asynchronous variant of the stochastic SCA algorithm which allows the use of surrogate calculated in earlier iterations. We characterize precise bound on the maximum delay the algorithm can tolerate, while still achieving the same convergence rate. We apply the algorithm to the problem of linear precoding in wireless sensor networks, where it can be implemented at low complexity but is shown to perform well in practice. [ABSTRACT FROM AUTHOR]

We study a new stochastic multi-player multi-armed bandits (MP-MAB) problem, where the reward distribution changes if a collision occurs on the arm. Existing literature always assumes a zero reward for involved players if collision happens, but for applications such as cognitive radio, the more realistic scenario is that collision reduces the mean reward but not necessarily to zero. We focus on the more practical no-sensing setting where players do not perceive collisions directly, and propose the Error-Correction Collision Communication (EC3) algorithm that models implicit communication as a reliable communication over noisy channel problem, for which random coding error exponent is used to establish the optimal regret that no communication protocol can beat. Finally, optimizing the tradeoff between code length and decoding error rate leads to a regret that approaches the centralized MP-MAB regret, which represents a natural lower bound. Experiments with practical error-correction codes on both synthetic and real-world datasets demonstrate the superiority of EC3. In particular, the results show that the choice of coding schemes has a profound impact on the regret performance. [ABSTRACT FROM AUTHOR]

Learning the joint probability of random variables (RVs) is the cornerstone of statistical signal processing and machine learning. However, direct nonparametric estimation for high-dimensional joint probability is in general impossible, due to the curse of dimensionality. Recent work has proposed to recover the joint probability mass function (PMF) of an arbitrary number of RVs from three-dimensional marginals, leveraging the algebraic properties of low-rank tensor decomposition and the (unknown) dependence among the RVs. Nonetheless, accurately estimating three-dimensional marginals can still be costly in terms of sample complexity, affecting the performance of this line of work in practice in the sample-starved regime. Using three-dimensional marginals also involves challenging tensor decomposition problems whose tractability is unclear. This work puts forth a new framework for learning the joint PMF using only pairwise marginals, which naturally enjoys a lower sample complexity relative to the third-order ones. A coupled nonnegative matrix factorization (CNMF) framework is developed, and its joint PMF recovery guarantees under various conditions are analyzed. Our method also features a Gram–Schmidt (GS)-like algorithm that exhibits competitive runtime performance. The algorithm is shown to provably recover the joint PMF up to bounded error in finite iterations, under reasonable conditions. It is also shown that a recently proposed economical expectation maximization (EM) algorithm guarantees to improve upon the GS-like algorithm's output, thereby further lifting up the accuracy and efficiency. Real-data experiments are employed to showcase the effectiveness. [ABSTRACT FROM AUTHOR]

We propose an interpretable graph neural network framework to denoise single or multiple noisy graph signals. The proposed graph unrolling networks expand algorithm unrolling to the graph domain and provide an interpretation of the architecture design from a signal processing perspective. We unroll an iterative denoising algorithm by mapping each iteration into a single network layer where the feed-forward process is equivalent to iteratively denoising graph signals. We train the graph unrolling networks through unsupervised learning, where the input noisy graph signals are used to supervise the networks. By leveraging the learning ability of neural networks, we adaptively capture appropriate priors from input noisy graph signals. A core component of graph unrolling networks is the edge-weight-sharing graph convolution operation, which parameterizes each edge weight by a trainable kernel function whose trainable parameters are shared by all the edges. The proposed convolution is permutation-equivariant and can flexibly adjust the edge weights to various graph signals. We further consider two special cases of this class of networks, graph unrolling sparse coding (GUSC) and graph unrolling trend filtering (GUTF), by unrolling sparse coding and trend filtering, respectively. To validate the proposed methods, we conduct extensive experiments on both real-world datasets and simulated datasets, and demonstrate that our methods have smaller denoising errors than conventional denoising algorithms and state-of-the-art graph neural networks. For denoising a single smooth graph signal, the normalized mean square error of the proposed networks is around 40% and 60% lower than that of graph Laplacian denoising and graph wavelets, respectively. [ABSTRACT FROM AUTHOR]

We study distributed composite optimization over networks: agents minimize a sum of smooth (strongly) convex functions–the agents’ sum-utility–plus a nonsmooth (extended-valued) convex one. We propose a general unified algorithmic framework for such a class of problems and provide a convergence analysis leveraging the theory of operator splitting. Distinguishing features of our scheme are: (i) When each of the agent’s functions is strongly convex, the algorithm converges at a linear rate, whose dependence on the agents’ functions and network topology is decoupled; (ii) When the objective function is convex (but not strongly convex), similar decoupling as in (i) is established for the coefficient of the proved sublinear rate. This also reveals the role of function heterogeneity on the convergence rate. (iii) The algorithm can adjust the ratio between the number of communications and computations to achieve a rate (in terms of computations) independent on the network connectivity; and (iv) A by-product of our analysis is a tuning recommendation for several existing (non-accelerated) distributed algorithms yielding provably faster (worst-case) convergence rate for the class of problems under consideration. [ABSTRACT FROM AUTHOR]

In this work, a gradient-based primal-dual method of multipliers is proposed for solving a class of linearly constrained non-convex problems. We show that with random initialization of the primal and dual variables, the algorithm is able to compute second-order stationary points (SOSPs) with probability one. Further, we present applications of the proposed method in popular signal processing and machine learning problems such as decentralized matrix factorization and decentralized training of overparameterized neural networks. One of the key steps in the analysis is to construct a new loss function for these problems such that the required convergence conditions (especially the gradient Lipschitz conditions) can be satisfied without changing the global optimal points. [ABSTRACT FROM AUTHOR]

This work focuses on the problem of unraveling nonlinearly mixed latent components in an unsupervised manner. The latent components are assumed to reside in the probability simplex, and are transformed by an unknown post-nonlinear mixing system. This problem finds various applications in signal and data analytics, e.g., nonlinear hyperspectral unmixing, image embedding, and nonlinear clustering. Linear mixture learning problems are already ill-posed, as identifiability of the target latent components is hard to establish in general. With unknown nonlinearity involved, the problem is even more challenging. Prior work offered a function equation-based formulation for provable latent component identification. However, the identifiability conditions are somewhat stringent and unrealistic. In addition, the identifiability analysis is based on the infinite sample (i.e., population) case, while the understanding for practical finite sample cases has been elusive. Moreover, the algorithm in the prior work trades model expressiveness with computational convenience, which often hinders the learning performance. Our contribution is threefold. First, new identifiability conditions are derived under largely relaxed assumptions. Second, comprehensive sample complexity results are presented—which are the first of the kind. Third, a constrained autoencoder-based algorithmic framework is proposed for implementation, which effectively circumvents the challenges in the existing algorithm. Synthetic and real experiments corroborate our theoretical analyses. [ABSTRACT FROM AUTHOR]

Carrier frequency offset (CFO) and channel estimation is a classic topic with a large body of prior work using the maximum likelihood (ML) approach together with the Cramér-Rao lower bound (CRLB) analysis. We give the maximum a posteriori probability (MAP) estimation solution, which is particularly useful for tracking. Unlike the ML cases, the corresponding Bayesian CRLB (BCRLB) shows a clear relation with parameters and low complexity algorithms are provided to achieve the BCRLB in almost all SNR range. Among them, the universal algorithm takes a new approach and avoids error floors of the traditional approach. We assume that the time invariant MIMO channel within a packet can have spatial correlation and nonzero mean. The estimation is based on pilot signals. An unexpected result is that the joint MAP estimation is equivalent to an individual MAP estimation of the frequency offset first, again different from the ML results. We provide insight on the pilot/training signal design based on the BCRLB. Unlike past algorithms that trade performance and/or complexity for the accommodation of time varying channels, the MAP solution provides a different route for dealing with time variation. Within a short enough (segment of) packet where the channel and CFO are approximately time invariant, the low complexity algorithm can be employed. Similar to the belief propagation, the estimation of the previous (segment of) packet can serve as the prior knowledge for the next (segment of) packet. [ABSTRACT FROM AUTHOR]

This article proposes a new class of Real Elliptically Skewed (RESK) distributions and associated clustering algorithms that integrate robustness and skewness into a single unified cluster analysis framework. Non-symmetrically distributed and heavy-tailed data clusters have been reported in a variety of real-world applications. Robustness is essential because a few outlying observations can severely obscure the cluster structure. The RESK distributions are a generalization of the Real Elliptically Symmetric (RES) distributions. To estimate the cluster parameters and memberships, we derive an expectation maximization (EM) algorithm for arbitrary RESK distributions. Special attention is given to a new robust skew-Huber M-estimator, which is also the approximate maximum likelihood estimator (MLE) for the skew-Huber distribution, that belongs to the RESK class. Numerical experiments on simulated and real-world data confirm the usefulness of the proposed methods for skewed and heavy-tailed data sets. [ABSTRACT FROM AUTHOR]

We focus on over-the-air (OTA) Federated Learning (FL), which has been suggested recently to reduce the communication overhead of FL due to the repeated transmissions of the model updates by a large number of users over the wireless channel. In OTA FL, all users simultaneously transmit their updates as analog signals over a multiple access channel, and the server receives a superposition of the analog transmitted signals. However, this approach results in the channel noise directly affecting the optimization procedure, which may degrade the accuracy of the trained model. We develop a Convergent OTA FL (COTAF) algorithm which enhances the common local stochastic gradient descent (SGD) FL algorithm, introducing precoding at the users and scaling at the server, which gradually mitigates the effect of noise. We analyze the convergence of COTAF to the loss minimizing model and quantify the effect of a statistically heterogeneous setup, i.e. when the training data of each user obeys a different distribution. Our analysis reveals the ability of COTAF to achieve a convergence rate similar to that achievable over error-free channels. Our simulations demonstrate the improved convergence of COTAF over vanilla OTA local SGD for training using non-synthetic datasets. Furthermore, we numerically show that the precoding induced by COTAF notably improves the convergence rate and the accuracy of models trained via OTA FL. [ABSTRACT FROM AUTHOR]