Search

In the pathway to 2030 electricity generation decarbonization and 2050 net-zero economies, scalable integration of distributed load can support environmental goals and also help alleviate smart grid operational issues through its electricity market participation. In this work, a novel Stackelberg game theoretic framework is proposed for trading the energy bidirectionally between the demand-response (DR) aggregator and the prosumers (distributed load). This formulation allows for flexible energy arbitrage and additional monetary rewards while ensuring that the prosumers’ desired daily energy demand is met. Then, a scalable (linear with the number of prosumers and the number of learning samples), the decentralized privacy-preserving algorithm is proposed to find approximate equilibria with online sampling and learning of the prosumers’ cumulative best response, which finds applications beyond this energy game. Moreover, cost bounds are provided on the quality of the approximate equilibrium solution. Finally, the real data from the California day-ahead market and the UC Davis campus building energy demands are utilized to demonstrate the efficacy of the proposed framework and the algorithm.

We consider the problem of collectively transporting multiple objects using air–ground multirobot teams. The objective is to find the optimal matching between the objects and aerial/ground robots that minimizes the energy of the overall system. We reveal the local optimality criteria for this combinatorial problem and prove that combining a branch and bound algorithm with a negative-cycle canceling algorithm (NCCA) yields an efficient algorithm that provides the globally optimal solution of the problem. Numerical experiments demonstrate the performance on practical problems.

Low-rank matrix models have been universally useful for numerous applications, from classical system identification to more modern matrix completion in signal processing and statistics. The nuclear norm has been employed as a convex surrogate of the low-rankness since it induces a low-rank solution to inverse problems. While the nuclear norm for low rankness has an excellent analogy with the $\ell _1$norm for sparsity through the singular value decomposition, other matrix norms also induce low-rankness. Particularly as one interprets a matrix as a linear operator between Banach spaces, various tensor product norms generalize the role of the nuclear norm. We provide a tensor-norm-constrained estimator for the recovery of approximately low-rank matrices from local measurements corrupted with noise. A tensor-norm regularizer is designed to adapt to the local structure. We derive statistical analysis of the estimator over matrix completion and decentralized sketching by applying Maurey’s empirical method to tensor products of Banach spaces. The estimator provides a near-optimal error bound in a minimax sense and admits a polynomial-time algorithm for these applications.

Actor–critic style two-time-scale algorithms are one of the most popular methods in reinforcement learning, and have seen great empirical success. However, their performance is not completely understood theoretically. In this article, we characterize the global convergence of an online natural actor–critic algorithm in the tabular setting using a single trajectory of samples. Our analysis applies to very general settings, as we only assume ergodicity of the underlying Markov decision process. In order to ensure enough exploration, we employ an $\epsilon$-greedy sampling of the trajectory. For a fixed and small enough exploration parameter $\epsilon$, we show that the two-time-scale natural actor–critic algorithm has a rate of convergence of $\tilde{\mathcal {O}}(1/T^{1/4})$, where $T$ is the number of samples, and this leads to a sample complexity of $\tilde{\mathcal {O}}(1/\delta ^{8})$ samples to find a policy that is within an error of $\delta$ from the global optimum. Moreover, by carefully decreasing the exploration parameter $\epsilon$ as the iterations proceed, we present an improved sample complexity of $\tilde{\mathcal {O}}(1/\delta ^{6})$ for convergence to the global optimum.

In this article, we study a decentralized variant of stochastic approximation (SA), a data-driven approach for finding the root of an operator under noisy measurements. A network of agents, each with its own operator and data observations, cooperatively find the fixed point of the aggregate operator over a decentralized communication graph. Our main contribution is to provide a finite-time analysis of this decentralized SA method when the data observed at each agent are sampled from a Markov process; this lack of independence makes the iterates biased and (potentially) unbounded. Under fairly standard assumptions, we show that the convergence rate of the proposed method is essentially the same as if the samples were independent, differing only by a log factor that accounts for the mixing time of the Markov processes. The key idea in our analysis is to introduce a novel Lyapunov–Razumikhin function, motivated by the one used in analyzing the stability of delayed ordinary differential equations. We also discuss applications of the proposed method on a number of interesting learning problems in multiagent systems.

We present novel analysis and algorithms for solving sparse phase retrieval and sparse principal component analysis (PCA) with convex lifted matrix formulations. The key innovation is a new mixed atomic matrix norm that, when used as regularization, promotes low-rank matrices with sparse factors. We show that convex programs with this atomic norm as a regularizer provide near-optimal sample complexity and error rate guarantees for sparse phase retrieval and sparse PCA. While we do not know how to solve the convex programs exactly with an efficient algorithm, for the phase retrieval case we carefully analyze the program and its dual and thereby derive a practical heuristic algorithm. We show empirically that this practical algorithm performs similarly to existing state-of-the-art algorithms.

We study gradient methods for solving distributed convex optimization problems over a network when the communication bandwidth between the nodes is limited, and so information that is exchanged between the nodes must be quantized. This imperfect communication poses a fundamental challenge, and if not properly accounted for may prevent the convergence of these algorithms. Our first contribution in this article is to propose a modified consensus-based gradient method for solving such problems using random (dithered) quantization. This algorithm can be interpreted as a distributed variant of a two-time-scale stochastic approximation algorithm. We then study the convergence and derive upper bounds on the rates of convergence of the proposed method as a function of the bandwidth available between the nodes and the underlying network topology for both convex and strongly convex objective functions. Our results complement existing literature, where such convergence and explicit formulas of the convergence rates are missing. Finally, we provide numerical simulations to compare the convergence properties of the distributed gradient methods with and without quantization for solving the well-known regression problems over networks, for both quadratic and absolute loss functions. [ABSTRACT FROM AUTHOR]

We study distributed optimization problems over a network when the communication between the nodes is constrained, and therefore, information that is exchanged between the nodes must be quantized. Recent advances using the distributed gradient algorithm with a quantization scheme at a fixed resolution have established convergence, but at rates significantly slower than when the communications are unquantized. In this article, we introduce a novel quantization method, which we refer to as adaptive quantization, that allows us to match the convergence rates under perfect communications. Our approach adjusts the quantization scheme used by each node as the algorithm progresses: as we approach the solution, we become more certain about where the state variables are localized and adapt the quantizer codebook accordingly. We bound the convergence rates of the proposed method as a function of the communication bandwidth, the underlying network topology, and structural properties of the constituent objective functions. In particular, we show that if the objective functions are convex or strongly convex, then using adaptive quantization does not affect the rate of convergence of the distributed subgradient methods when the communications are quantized, except for a constant that depends on the resolution of the quantizer. To the best of our knowledge, the rates achieved in this article are better than any existing work in the literature for distributed gradient methods under finite communication bandwidths. We also provide numerical simulations that compare convergence properties of the distributed gradient methods with and without quantization for solving distributed regression problems for both quadratic and absolute loss functions. [ABSTRACT FROM AUTHOR]

We study the low-rank phase retrieval problem, where our goal is to recover a $d_1\times d_2$low-rank matrix from a series of phaseless linear measurements. This is a fourth-order inverse problem, as we are trying to recover factors of a matrix that have been observed, indirectly, through some quadratic measurements. We propose a solution to this problem using the recently introduced technique of anchored regression. This approach uses two different types of convex relaxations: we replace the quadratic equality constraints for the phaseless measurements by a search over a polytope and enforce the rank constraint through nuclear norm regularization. The result is a convex program in the space of $d_1 \times d_2$matrices. We analyze two specific scenarios. In the first, the target matrix is rank-$1$, and the observations are structured to correspond to a phaseless blind deconvolution. In the second, the target matrix has general rank, and we observe the magnitudes of the inner products against a series of independent Gaussian random matrices. In each of these problems, we show that anchored regression returns an accurate estimate from a near-optimal number of measurements given that we have access to an anchor matrix of sufficient quality. We also show how to create such an anchor in the phaseless blind deconvolution problem from an optimal number of measurements and present a partial result in this direction for the general rank problem.

The increase in the number of edge devices has led to the emergence of edge computing where the computations are performed on the device. In recent years, deep neural networks (DNNs) have become the state-of-the-art method in a broad range of applications, from image recognition, to cognitive tasks to control. However, neural network models are typically large and computationally expensive and therefore not deployable on power and memory constrained edge devices. Sparsification techniques have been proposed to reduce the memory foot-print of neural network models. However, they typically lead to substantial hardware and memory overhead. In this article, we propose a hardware-aware pruning method using linear feedback shift register (LFSRs) to generate the locations of non-zero weights in real-time during inference. We call this LFSR-generated pseudo-random sequence based sparsity (LGPS) technique. We explore two different architectures for our hardware-friendly LGPS technique, based on (1) row/column indexing with LFSRs and (2) column-wise indexing with nested LFSRs, respectively. Using the proposed method, we present a total saving of energy and area up to 37.47% and 49.93% respectively and speed up of $1.53\times $ w.r.t the baseline pruning method, for the VGG-16 network on down-sampled ImageNet. [ABSTRACT FROM AUTHOR]

Given a collection of parameterized multi-robot controllers associated with individual behaviors designed for particular tasks, this paper considers the problem of how to sequence and instantiate the behaviors for the purpose of completing a more complex, overarching mission. In addition, uncertainties about the environment or even the mission specifications may require the robots to learn, in a cooperative manner, how best to sequence the behaviors. In this paper, we approach this problem by using reinforcement learning to approximate the solution to the computationally intractable sequencing problem, combined with an online gradient descent approach to selecting the individual behavior parameters, while the transitions among behaviors are triggered automatically when the behaviors have reached a desired performance level relative to a task performance cost. To illustrate the effectiveness of the proposed method, it is implemented on a team of differential-drive robots for solving two different missions, namely, convoy protection and object manipulation.

Advanced power amplifier (PA) architectures are critical for 5G communication which requires PAs to have sufficient output power, high linearity, and high energy efficiency. The time-variant operational environment further demands the self-reconfigurability in the PA design. Recent developments in bandit-problems and reinforcement learning (RL) have led to data-driven control algorithms. This paper presents various RL-based algorithms for Doherty PA control, which achieve robust adaptive operation over environmental changes. Multiple RL frameworks are incorporated in the control algorithms including multi-armed bandit (MAB), continuum-armed bandit (CAB), contextual-bandit (CB), and actor-critic with experience replay (AC). The control algorithms based on the latter three frameworks leverage on the prior information about the Doherty PA’s characteristics to improve learning efficiency. In our simulation test where the optimal policy needs to be adjusted due to transmitter output load impedance mismatch, the MAB-based control learns the optimal policy within 25,000 samples. The control algorithms based on CAB and CB learn the optimal policy within 5,000 samples. The fastest learning rate is achieved by the control algorithm based on AC, which learns the optimal policy within 1,500 samples. [ABSTRACT FROM AUTHOR]

Motivated by broad applications within engineering and sciences, we study distributed consensus-based gradient methods for solving optimization problems over a network of nodes. A fundamental challenge for solving this problem is the impact of finite communication bandwidth, so information that is exchanged between the nodes must be quantized. In this paper, we utilize the dithered (random) quantization and study the distributed variant of the well-known two-time-scale methods for solving the underlying optimization problems under the constraint of finite bandwidths. In addition, we provide more insight and an explicit formula of how to design the step sizes of these two-time-scale methods and their impacts on the performance of the algorithms.

In this paper, we consider the problem of estimating simultaneously low-rank and row-wise sparse matrices from nested linear measurements, where the linear operator consists of the product of a linear operator $\mathcal {W}$and a matrix $\boldsymbol {\varPsi }$. Leveraging the nested structure of the measurement operator, we propose a computationally efficient two-stage algorithm for estimating the simultaneously structured target matrix. Assuming that $\mathcal {W}$is a restricted isometry for low-rank matrices and $\boldsymbol {\varPsi }$is a restricted isometry for row-wise sparse matrices, we establish an accuracy guarantee that holds uniformly for all sufficiently low-rank and row-wise sparse matrices with high probability. Furthermore, using standard tools from information theory, we establish a minimax lower bound for estimation of simultaneously low-rank and row-wise sparse matrices from linear measurements that need not be nested. The accuracy bounds established for the algorithm, that also serve as a minimax upper bound, differ from the derived minimax lower bound merely by a polylogarithmic factor of the dimensions. Therefore, the proposed algorithm is nearly minimax optimal. We also discuss some applications of the proposed observation model and evaluate our algorithm through numerical simulation.

Inspection and imaging through scattering layers is a decades-old problem in optics. Unlike x-ray and ultrasonic imaging techniques, time-domain spectroscopy methods can provide detailed chemical and structural information of subsurfaces along with their depth. Although high-resolution time-of-flight measurement in time-domain spectroscopy provides 3D information, unfortunately it also induces an unwanted sensitivity to misalignments of the system and distortion of the layers themselves. Such high sensitivity to alignment and sample surface is a well known problem in time-domain and interferometric imaging, and is a major concern when the alignment error is comparable to the pulse wavelength. Here, we propose and implement an algorithmic framework based on low-rank matrix recovery and alternating minimization to remove such unwanted distortions from time-domain images. The method allows for recovery of the original sample texture in spite of the presence of temporal-spatial distortions. We address a blind-demodulation problem where, based on several observations of the sample texture modulated by undesired sweep distortions, the two classes of signals are separated with minimal damage to the main features. The performance of the method is examined in both synthetic and real data in the case of a terahertz time-domain system, and the successful reconstructions are demonstrated. The proposed general scheme can be implemented to advance inspection and imaging applications in THz and other time-resolved spectral imaging modalities.

In this paper we present a complete (hardware/ software) sub-Nyquist rate (× 13) wideband signal acquisition chain capable of acquiring radar pulse parameters in an instantaneous bandwidth spanning 100 MHz-2.5 GHz with the equivalent of 8 effective number of bits (ENOB) digitizing performance. The approach is based on the alternative sensing-paradigm of compressed sensing (CS). The hardware platform features a fully-integrated CS receiver architecture named the random-modulation preintegrator (RMPI) fabricated in Northrop Grumman's 450 nm InP HBT bipolar technology. The software back-end consists of a novel CS parameter recovery algorithm which extracts information about the signal without performing full time-domain signal reconstruction. This approach significantly reduces the computational overhead involved in retrieving desired information which demonstrates an avenue toward employing CS techniques in power-constrained real-time applications. The developed techniques are validated on CS samples physically measured by the fabricated RMPI and measurement results are presented. The parameter estimation algorithms are described in detail and a complete description of the physical hardware is given.

We present a wide bandwidth, compressed sensing based nonuniform sampling (NUS) system with a custom sample-and-hold chip designed to take advantage of a low average sampling rate. By sampling signals nonuniformly, the average sample rate can be more than a magnitude lower than the Nyquist rate, provided that these signals have a relatively low information content as measured by the sparsity of their spectrum. The hardware design combines a wideband Indium-Phosphide heterojunction bipolar transistor sample-and-hold with a commercial off-the-shelf analog-to-digital converter to digitize an 800 MHz to 2 GHz band (having 100 MHz of noncontiguous spectral content) at an average sample rate of 236 Ms/s. Signal reconstruction is performed via a nonlinear compressed sensing algorithm, and the challenges of developing an efficient implementation are discussed. The NUS system is a general purpose digital receiver. As an example of its real signal capabilities, measured bit-error-rate data for a GSM channel is presented, and comparisons to a conventional wideband 4.4 Gs/s ADC are made.

This document provides a correction to the proof of the theorem establishing the exponential speed of convergence of the Locally Competitive Algorithm (LCA) in the paper “Convergence and Rate Analysis of Neural Networks for Sparse Approximation.” [ABSTRACT FROM AUTHOR]

We consider the general problem of matching a subspace to a signal in $\mathbb {R}^N$ that has been observed in-directly (compressed) through a random projection. We are interested in the case where the collection of $K$-dimensional subspaces is continuously parameterized, i.e. naturally indexed by an interval from the real line, or more generally a region of $\mathbb {R}^D$. Our main results show that if the dimension of the random projection is on the order of $K$ times, a geometrical constant that describes the complexity of the collection, then the match obtained from the compressed observation is nearly as good as one obtained from a full observation of the signal. We give multiple concrete examples of collections of subspaces for which this geometrical constant can be estimated, and discuss the relevance of the results to the general problems of template matching and source localization.