Search

As an algorithmic framework, message passing is extremely powerful and has wide applications in the context of different disciplines including communications, coding theory, statistics, signal processing, artificial intelligence and combinatorial optimization. In this paper, we investigate the performance of a message-passing algorithm called min-sum belief propagation (BP) for the vertex-disjoint shortest $k$ -path problem ($k$ -VDSP) on weighted directed graphs, and derive the iterative message-passing update rules. As the main result of this paper, we prove that for a weighted directed graph $G$ of order $n$ , BP algorithm converges to the unique optimal solution of $k$ -VDSP on $G$ within $O(n^{2}w_{max})$ iterations, provided that the weight $w_{e}$ is nonnegative integral for each arc $e\in E(G)$ , where $w_{max}=\max \{w_{e}: e\in E(G)\}$. To the best of our knowledge, this is the first instance where BP algorithm is proved correct for NP-hard problems. Additionally, we establish the extensions of $k$ -VDSP to the case of multiple sources or sinks. [ABSTRACT FROM AUTHOR]

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]

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 ability of an algorithm to extract power quality parameters on a low-end digital controller with constrained resources and computational capacity can promote comprehensive adoption of power quality control and monitoring infrastructure because of reduced cost and thus improve operational ability in a microgrid or distribution grid and support more in-depth integration of renewable energy. Since conventional harmonic extraction for single-phase grid mostly operate on Fourier transform, lock-in amplifier and their derivative algorithms, they demand large memory and computational power which are available with high-end application-specific processors, digital signal processors (DSPs) and field programmable gate arrays (FPGAs). In this paper, a computationally efficient harmonic extraction algorithm is proposed, which can be implemented on commercially available microcontrollers with ease, without compromising accuracy. A detailed theoretical analysis of the proposed method, along with various simulation and the experimental results are presented. Workarounds for minor implementation issues on digital controllers are discussed as well. [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]

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]

–This paper proposes an efficient and optimal reduced control set model predictive flux control (RCS-MPFC) for a three-level neutral-point-clamped voltage source inverter (3L-NPC VSI) fed induction motor. The proposed algorithm reduces the computational time in the prediction stage without causing any suboptimality. The optimal voltage vector selected by the proposed method produces the same cost function value as that of the conventional FCS-MPFC which requires enumerating all 27 voltage vectors. Therefore, the proposed algorithm achieves the same performance as the conventional method in the entire range of operation of IM drives while the computational effort is significantly reduced. Experimental results verify the effectiveness of the proposed algorithm and its superior performance compared to the existing RCS-MPFC scheme. [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]

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]

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]

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]

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]

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]

Future wireless networks need to support massive machine type communication (mMTC) where a massive number of devices accesses the network and massive MIMO is a promising enabling technology. Massive access schemes have been studied for co-located massive MIMO arrays. In this paper, we investigate the activity detection in grant-free random access for mMTC in cell-free massive MIMO networks using distributed arrays. Each active device transmits a non-orthogonal pilot sequence to the access points (APs) and the APs send the received signals to a central processing unit (CPU) for joint activity detection. The maximum likelihood device activity detection problem is formulated and algorithms for activity detection in cell-free massive MIMO are provided to solve it. The simulation results show that the macro diversity gain provided by the cell-free architecture improves the activity detection performance compared to co-located architecture when the coverage area is large. [ABSTRACT FROM AUTHOR]

A deep learning assisted sum-product detection algorithm (DL-SPDA) for faster-than-Nyquist (FTN) signaling is proposed in this paper. The proposed detection algorithm works on a modified factor graph which concatenates a neural network function node to the variable nodes of the conventional FTN factor graph to approach the maximum a posterior probabilities (MAP) error performance. In specific, the neural network performs as a function node in the modified factor graph to deal with the residual intersymbol interference (ISI) that is not considered by the conventional detector with a limited complexity. We modify the updating rule in the conventional sum-product algorithm so that the neural network assisted detector can be complemented to a turbo equalization receiver. Furthermore, we propose a compatible training technique to improve the detection performance of the proposed DL-SPDA with turbo equalization. In particular, the neural network is optimized in terms of the mutual information between the transmitted sequence and the extrinsic information. We also investigate the maximum-likelihood bit error rate (BER) performance of a finite length coded FTN system. Simulation results show that the error performance of the proposed algorithm approaches the MAP performance, which is consistent with the analytical BER. [ABSTRACT FROM AUTHOR]

Coupled Matrix Tensor Factorization (CMTF) facilitates the integration and analysis of multiple data sources and helps discover meaningful information. Nonnegative CMTF (N-CMTF) has been employed in many applications for identifying latent patterns, prediction, and recommendation. However, due to the added complexity with coupling between tensor and matrix data, existing N-CMTF algorithms exhibit poor computation efficiency. In this paper, a computationally efficient N-CMTF factorization algorithm is presented based on the column-wise element selection, preventing frequent gradient updates. Theoretical and empirical analyses show that the proposed N-CMTF factorization algorithm is not only more accurate but also more computationally efficient than existing algorithms in approximating the tensor as well as in identifying the underlying nature of factors. [ABSTRACT FROM AUTHOR]

Color demosaicing is an essential step in the camera image processing pipeline, especially on hardware platforms for real-time video applications. Though many demosaicing algorithms have been proposed in the past two decades, there remains a substantial gap between industrial needs and academic research. On one hand, industry requires a high perceptual quality, artifact-free, and low-cost demosaicing algorithm that is noniterative and small window based ready to be implemented on a hardware platform with a limited line buffer. On the other hand, academia is targeting high PSNR/SSIM, with the computation cost and line buffer receiving second priority, and often a frame buffer and iterative operation are used. The cost, large line buffer and iteration requirement make most existing demosaicing algorithms inapplicable on hardware platforms. In this paper, we introduce a novel low-cost demosaicing algorithm to narrow the gap. We keep the operation window size and computation cost as the first priority and achieve both high PSNR/SSIM and visual perceptual quality compared to previous state-of-the-art methods on standard test datasets. We fully investigate the a priori knowledge of natural scene raw images and find several key cues that are beneficial to demosaicing. Our demosaicing algorithm is a smart fusion of these useful cues. Furthermore, we solve typical demosaicing issues that occur in many traditional methods, including false color artifacts, T-section closing, and zippering artifacts. The proposed method has no learning stage, no iteration operation, a small line buffer and a limited number of parameters, so it can easily be applied to hardware platforms. [ABSTRACT FROM AUTHOR]

We propose a holographic version of a reconfigurable intelligent surface (RIS) and investigate its application to terahertz (THz) massive multiple-input multiple-output systems. Capitalizing on the miniaturization of THz electronic components, RISs can be implemented by densely packing sub-wavelength unit cells, so as to realize continuous or quasi-continuous apertures and to enable holographic communications. In this paper, in particular, we derive the beam pattern of a holographic RIS. Our analysis reveals that the beam pattern of an ideal holographic RIS can be well approximated by that of an ultra-dense RIS, which has a more practical hardware architecture. In addition, we propose a closed-loop channel estimation (CE) scheme to effectively estimate the broadband channels that characterize THz massive MIMO systems aided by holographic RISs. The proposed CE scheme includes a downlink coarse CE stage and an uplink finer-grained CE stage. The uplink pilot signals are judiciously designed for obtaining good CE performance. Moreover, to reduce the pilot overhead, we introduce a compressive sensing-based CE algorithm, which exploits the dual sparsity of THz MIMO channels in both the angular domain and delay domain. Simulation results demonstrate the superiority of holographic RISs over the non-holographic ones, and the effectiveness of the proposed CE scheme. [ABSTRACT FROM AUTHOR]

In this paper, we consider the downlink (DL) of a zero-forcing (ZF) precoded extra-large scale massive MIMO (XL-MIMO) system. The base-station (BS) operates with limited number of radio-frequency (RF) transceivers due to high cost, power consumption and interconnection bandwidth associated to the fully digital implementation. The BS, which is implemented with a subarray switching architecture, selects groups of active antennas inside each subarray to transmit the DL signal. This work proposes efficient resource allocation (RA) procedures to perform joint antenna selection (AS) and power allocation (PA) to maximize the DL spectral efficiency (SE) of an XL-MIMO system operating under different loading settings. Two metaheuristic RA procedures based on the genetic algorithm (GA) are assessed and compared in terms of performance, coordination data size and computational complexity. One algorithm is based on a quasi-distributed methodology while the other is based on the conventional centralized processing. Numerical results demonstrate that the quasi-distributed GA-based procedure results in a suitable trade-off between performance, complexity and exchanged coordination data. At the same time, it outperforms the centralized procedures with appropriate system operation settings. [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]