In this paper, we analyze the performance of cooperative spectrum sharing single-carrier (SC) relay systems. Taking into account the peak interference power at the primary user (PU) and the maximum transmit power at the secondary user (SU) network, two separate power allocation constraints are formed. For a two-hop decode-and-forward (DF) relaying protocol and two power allocation constraints, two relay selection schemes, namely, a full-channel state information (CSI)-based best relay selection (BRS) and a partial CSI-based best relay selection (PBRS), are proposed. The distributions of the end-to-end signal-to-noise ratios (e2e-SNRs) for the four cases are derived first, and then their outage probabilities and asymptotic outage probabilities are derived in closed-form. The derived asymptotic outage probabilities are utilized to see different diversity gains. Monte Carlo simulations have verified the derived diversity gains for the four different cases. We also present upper bounds on the ergodic capacities for two particular cases.
The entropy computation of Gaussian mixture distributions with a large number of components has a prohibitive computational complexity. In this paper, we propose a novel approach exploiting the sphere decoding concept to bound and approximate such entropy terms with reduced complexity and good accuracy. Moreover, we propose an SNR region-based enhancement of the approximation method to reduce the complexity even further. Using Monte-Carlo simulations, the proposed methods are numerically demonstrated for the computation of the mutual information including the entropy term of various channels with finite constellation modulations such as binary and quadratic amplitude modulation (QAM) inputs for communication applications.
The problem of source-channel coding over a multiple-antenna (MIMO) channel with quantized channel state information at the transmitter (CSIT) is considered. Upper bounds on the distortion exponents achieved with partial CSIT under a long-term power constraint are developed. It is shown that the distortion exponent with perfect CSIT grows unbounded as the ratio between the channel and source bandwidth increases, while the exponent achieved with any feedback link of fixed, finite resolution is bounded above by a polynomial of the product between the number of transmit and number of receive antennas. The resolution of the feedback link should grow with the bandwidth ratio to make the distortion exponent scale as fast as that in the perfect-CSIT case. We show that in order to achieve the optimal scaling the CSIT feedback resolution must grow logarithmically with the bandwidth ratio for MIMO channels, and faster than linear for the single-input single-output channel. The achievable distortion exponent of some hybrid schemes with heavily quantized feedback is also derived. The results demonstrate that dramatic performance improvement over the case of no CSIT can be achieved by combining simple schemes with a very coarse CSIT feedback.
Transmit diversity, which was initially developed for noise-limited environments, has been promoted as a viable candidate for improving the link quality in both existing and future systems for wireless communication. However, to ensure efficient spectrum utilization, receivers operating within wireless multiuser networks must be robust not only to fading and noise but to interference from other system users as well. This work considers interference robustness aspects when transmit diversity, in the form of space-time block coding, is used in multiuser systems. Properties of the space-time block encoded signals such as code rate, block structure, diversity order, etc., and their implications on detection and interference rejection by means of noise whitening are discussed. To handle the presence of space-time block encoded interference, a space-time processing-based extension of an interference rejection combining algorithm is proposed. Results are presented indicating that transmit diversity based on space-time block codes (STBCs) of the linear dispersion type improve robustness against interference in terms of an increased diversity advantage. This can be achieved either by increasing the number of transmit antennas or by reducing the rate of the code. It is also shown, by analysis and by simulation examples, that the performance improvements obtained by using transmit diversity in multiuser systems may rapidly subside as the signal-to-interference ratio decreases. However, by using the proposed interference rejection scheme tailored to the space-time encoded structure, performance improvements of transmit diversity are also obtained in a multiuser environment.
The impact of interference is one of the most capacity limiting factors in cellular networks today. In order to host more users in existing systems and maximize the capacity of future networks, the use of interference suppression techniques are instrumental. In this paper, we propose a structured semi-blind parameter estimation procedure to support rejection, of unknown cochannel interference (CCI) in systems facing multipath channels with non-negligible delay spread. Employing spatio-temporal processing, the proposed scheme exploits the temporal correlation present in the output signal from an antenna array and the training data of a desired user in order to find parameter estimates that fit the range space of a structured CCI model to the signal subspace of the interfering signals. Simulation results illustrating the behavior of a spatio-temporal receiver using the proposed scheme with respect to both signal-to-noise and signal-to-interference ratios (SNRs and SIRs) are presented. In addition, results highlighting the impact of the training sequence length as well as the impact of the channel model order of the CCI users are also included.
The notion of a multiple description quantizer (MDQ) includes providing multiple distortion levels. If a human observer is involved, the design of MDQ requires a suitable distortion measure to achieve a graceful quality degradation in the case of description losses. While the mean squared error is a ubiquitous distortion measure for many classic MDQ schemes, it is known to be perceptually relevant only at low distortions. We propose a new MDQ designed according to an unconventional distortion criterion that combines the mean squared error with a constraint on the probability distribution of the reconstructed signal. The performance of the new MDQ is shown to approach that of the classic MDQ asymptotically as rate increases. However, once applied in the context of transform audio coding, the new MDQ significantly outperforms a classic MDQ in perceptual tests. The new scheme is suitable for a wide range of distortions and renders a seamless transition between coding that preserves signal features and coding of a waveform.
This paper investigates an optimal energy allocation problem for multisensor estimation of a random source where sensors communicate their measurements to a remote fusion center (FC) over orthogonal fading wireless channels using uncoded analog transmissions. The FC reconstructs the source using the best linear unbiased estimator (BLUE). The sensors have limited batteries but can harvest energy and also transfer energy to other sensors in the network. A distortion minimization problem over a finite-time horizon with causal and noncausal centralized information is studied and the optimal energy allocation policy for transmission and sharing is derived. Several structural necessary conditions for optimality are presented for the two sensor problem with noncausal information and a horizon of two time steps. A decentralized energy allocation algorithm is also presented where each sensor has causal information of its own channel gain and harvested energy levels and has statistical information about the channel gains and harvested energies of the remaining sensors. Various other suboptimal energy allocation policies are also proposed for reducing the computational complexity of dynamic programming based solutions to the energy allocation problems with causal information patterns. Numerical simulations are included to illustrate the theoretical results. These illustrate that energy sharing can reduce the distortion at the FC when sensors have asymmetric fading channels and asymmetric energy harvesting processes.
In this paper, we present a blind equalization algorithm for noisy IIR channels when the channel input is a finite state Markov chain. The algorithm yields estimates of the IIR channel coefficients, channel noise variance, transition probabilities, and state of the Markov chain. Unlike the optimal maximum likelihood estimator which is computationally infeasible since the computing cost increases exponentially with data length, our algorithm is computationally inexpensive. Our algorithm is based on combining a recursive hidden Markov model (HMM) estimator with a relaxed SPR (strictly positive real) extended least squares (ELS) scheme. In simulation studies we show that the algorithm yields satisfactory estimates even in low SNR. We also compare the performance of our scheme with a truncated FIR scheme and the constant modulus algorithm (CMA) which is currently a popular algorithm in blind equalization.
This paper uses stochastic dominance principles to construct upper and lower sample path bounds for Hidden Markov Model (HMM) filters. We consider an HMM consisting of an X-state Markov chain with transition matrix P. By using convex optimization methods for nuclear norm minimization with copositive constraints, we construct low rank stochastic matrices (P) under bar and (P) over bar so that the optimal filters using (P) under bar, (P) over bar provably lower and upper bound (with respect to a partially ordered set) the true filtered distribution at each time instant. Since (P) under bar and (P) over bar are low rank (say R), the computational cost of evaluating the filtering bounds is O(XR) instead of O(X-2). A Monte-Carlo importance sampling filter is presented that exploits these upper and lower bounds to estimate the optimal posterior. Finally, explicit bounds are given on the variational norm between the true posterior and the upper and lower bounds in terms of the Dobrushin coefficient.
Subspace-based methods for parameter identification have received considerable attention in the literature. Starting with a scalar-valued process, it is well known that subspace-based identification of sinusoidal frequencies is possible if the scalar valued data is windowed to form a low-rank vector-valued process. MUSIC and ESPRIT-like estimators have, for some time, been applied to this vector model. In addition, a statistically attractive Markov-like procedure for this class of methods has been proposed. Herein, the Markov-like procedure is reinvestigated. Several results regarding rank, performance, and structure are given in a compact manner. The large sample equivalence with the approximate maximum likelihood method by Stoica et al. (1988) is also established
Blind identification of single input multiple output systems is considered herein. The low-rank structure of the output signal is exploited to blindly identify the channel using a subspace fitting framework. Two approaches based on a minimal linear parameterization of a subspace are presented and analyzed. The asymptotically best consistent estimate is derived for the class of blind subspace-based techniques. The asymptotic estimation error covariance of the subspace estimates is derived, and the corresponding covariance of the statistically optimal estimates provides a lower bound on the estimation error covariance of subspace methods. A two-step procedure involving only linear systems of equations is presented that asymptotically achieves the bound. Simulations and numerical examples are provided to compare the two approaches.
A computationally efficient method for online joint state inference and dynamical model learning is presented. The dynamical model combines an a priori known, physically derived, state-space model with a radial basis function expansion representing unknown system dynamics and inherits properties from both physical and data-driven modeling. The method uses an extended Kalman filter approach to jointly estimate the state of the system and learn the unknown system dynamics, via the parameters of the basis function expansion. The key contribution is a computational complexity reduction compared to a similar approach with globally supported basis functions. By using compactly supported radial basis functions and an approximate Kalman gain, the computational complexity is considerably reduced and is essentially determined by the support of the basis functions. The approximation works well when the system dynamics exhibit limited correlation between points well separated in the state-space domain. The method is exemplified via two intelligent vehicle applications where it is shown to: (i) have competitive system dynamics estimation performance compared to the globally supported basis function method, and (ii) be real-time applicable to problems with a large-scale state-space.
This correspondence studies the problem of separating a signal of interest from co-channel interference for the situation when the number of co-channel users and their channels are unknown. We devise a novel approach to this problem based on a trained statistical mixture model. Numerical results illustrate that the new method can outperform conventional training-based multiuser detection.
In this correspondence we compute a closed-form expression for theasymptotic (large-sample) accuracy of the recently proposedsquared-range least-squares (SR-LS) method for source localization. We compare its accuracy to that of the classicalleast-squares (LS) method and show that LS and SR-LS performdifferently in general. We identify geometries where theperformances of the methods are identical but also geometries when thedifference in performance is unbounded.
This paper presents a new approach to soft demodulationfor MIMO channels. The proposed method is an approximationto the exact a posteriori probability-per-bit computer. Themain idea is to marginalize the posterior density for the receiveddata exactly over the subset of the transmitted bits that are receivedwith the lower signal-to-noise-ratio (SNR), and marginalize thisdensity approximately over the remaining bits. Unlike the exact demodulator,whose complexity is huge due to the need for enumeratingall possible combinations of transmitted constellation points,the proposed method has very low complexity. The algorithm hasa fully parallel structure, suitable for implementation in parallelhardware. Additionally, its complexity is fixed, which makes it suitablefor pipelined implementation. We also show how the methodcan be extended to the situation when the receiver has only partialchannel state information, and how it can be modified to takesoft-input into account. Numerical examples illustrate its performanceon slowly fading 4x4 and 6x6 complex MIMO channels.
We consider linear regression under a model where the parameter vector is known to be sparse. Using a Bayesian framework, we derive the minimum mean-square error (MMSE) estimate of the parameter vector, and a computationally efficient approximation of it. We also derive an empirical-Bayesian version of the estimator, which does not need any a priori information, nor does it need the selection of any user parameters. As a byproduct, we obtain a powerful model (``basis'') selection tool for sparse models. The performance and robustness of our new estimators are illustrated via numerical examples.
We consider linear regression under a model where the parameter vector is known to be sparse. Using a Bayesian framework, we derive the minimum mean-square error (MMSE) estimate of the parameter vector and a computationally efficient approximation of it. We also derive an empirical-Bayesian version of the estimator, which does not need any a priori information, nor does it need the selection of any user parameters. As a byproduct, we obtain a powerful model ("basis") selection tool for sparse models. The performance and robustness of our new estimators are illustrated via numerical examples.
This paper considers the problem of estimating the direction-of-arrival (DOA) of one or more signals using an array of sensors, where some of the sensors fail to work before the measurement is completed. Methods for estimating the array output covariance matrix are discussed. In particular, the maximum-likelihood (ML) estimate of this covariance matrix and its asymptotic accuracy are derived and discussed. Different covariance matrix estimates are used for DOA estimation together with the MUSIC algorithm and with a covariance matching technique. In contrast to MUSIC, the covariance matching technique can utilize information on the estimation accuracy of the array covariance matrix, and it is demonstrated that this yields a significant performance gain.
The amplitude and phase estimation (APES) approach to nonparametric spectrum estimation of uniformly sampled data has received considerable interest. We consider the extension of APES to gapped data, i.e., uniformly sampled data with missing samples. It has been shown that the APES estimate of the spectrum is the minimizer of a certain least-squares (LS) criterion, and our extension of APES is based on minimizing this LS criterion with respect to the missing data as well. A computationally efficient method for doing this based on cyclic minimization and the conjugate gradient algorithm is proposed. The new algorithm is called gapped-data APES (GAPES) and is developed for the two-dimensional (2-D) case, with the one-dimensional (1-D) case as a special instance. Numerical examples are provided to demonstrate the performance of the algorithm and to show the advantages of 2-D data processing over 1-D (row or column-wise) data processing, as well as to show the applicability of the algorithm to synthetic aperture radar (SAR) imaging.
Space-time coding (STC) schemes for communication systems employing multiple transmit and receive antennas have been attracting increased attention. In this paper, we address two interrelated problems: detection of space-time codes under various interference conditions and information transfer from the STC detector to an error-correcting channel decoder. By taking a systematic maximum-likelihood (ML) approach to the joint detection and decoding problem, we show how to design optimal detectors and how to integrate them with a channel decoder. We also discuss various aspects of channel modeling for STC communication receivers. In particular, while many previous works on space-time coding assume that the channel is a stochastic quantity, we findthat a deterministic channel model can have some advantages for the receiver design. Finally, we illustrate our results by numerical examples.
Space-time coding (STC) schemes for communication systems employing multiple transmit and receive antennas have been attracting increased attention. The so-called orthogonal space-time block codes (OSTBCs) have been of particular interest due to their good performance and low decoding complexity. In this paper, we take a systematic maximum-likelihood (ML) approach to the decoding of OSTBC for unknown propagation channels and unknown noise and interference conditions. We derive a low-complexity ML decoding algorithm based on cyclic minimization and assisted by a minimum amount of training data. Furthermore, we discuss the design of optimal training sequences and optimal information transfer to an outer decoder. Numerical examples demonstrate the performance of our algorithm.
In this paper, we consider optimal multiuser downlink beamforming in the presence of a massive number of arbitrary quadratic shaping constraints. We combine beamforming with full-rate high dimensional real-valued orthogonal space time block coding (OSTBC) to increase the number of beamforming weight vectors and associated degrees of freedom in the beamformer design. The original multi-constraint beamforming problem is converted into a convex optimization problem using semidefinite relaxation (SDR) which can be solved efficiently. In contrast to conventional (rank-one) beamforming approaches in which an optimal beamforming solution can be obtained only when the SDR solution (after rank reduction) exhibits the rank-one property, in our approach optimality is guaranteed when a rank of eight is not exceeded. We show that our approach can incorporate up to 79 additional shaping constraints for which an optimal beamforming solution is guaranteed as compared to a maximum of two additional constraints that bound the conventional rank-one downlink beamforming designs. Simulation results demonstrate the flexibility of our proposed beamformer design.
In this paper we consider state estimation of a discrete time linear system using multiple sensors, where the sensors quantize their individual innovations, which are then combined at the fusion center to form a global state estimate. We prove the stability of the estimation scheme under sufficiently high bit rates. We obtain asymptotic approximations for the error covariance matrix that relates the system parameters and quantization levels used by the different sensors. Numerical results show close agreement with the true error covariance for quantization at high rates. An optimal rate allocation problem amongst the different sensors is also considered.
Multiple-input-multiple-output (MIMO) radar is an emerging technology that has significant potential for advancing the state-of-the-art of modern radar. When orthogonal waveforms are transmitted, with M + N (N transmit and M receive) antennas, an MN-element filled virtual array can be obtained. To successfully utilize such an array for high-resolution MIMO radar imaging, constant-modulus transmit signal synthesis and optimal receive filter design play critical roles. We present in this paper a computationally attractive cyclic optimization algorithm for the synthesis of constant-modulus transmit signals with good auto- and cross-correlation properties. Then we go on to discuss the use of an instrumental variables approach to design receive filters that can be used to minimize the impact of scatterers in nearby range bins on the received signals from the range bin of interest (the so-called range compression problem). Finally, we present a number of numerical examples to demonstrate the effectiveness of the proposed approaches.
A multi-input multi-output (MIMO) radar system, unlike standard phased-array radar, can transmit via its antennas multiple probing signals that may be correlated or uncorrelated with each other. This waveform diversity offered by MIMO radar enables superior capabilities compared with a standard phased-array radar. One of the common practices in radar has been range compression. We first address the question of "to compress or not to compress" by considering both the Cramer-Rao bound (CRB) and the sufficient statistic for parameter estimation. Next, we consider MIMO radar waveform optimization for parameter estimation for the general case of multiple targets in the presence of spatially colored interference and noise. We optimize the probing signal vector of a MIMO radar system by considering several design criteria, including minimizing the trace, determinant, and the largest eigenvalue of the CRB matrix. We also consider waveform optimization by minimizing the CRB of one of the target angles only or one of the target amplitudes only. Numerical examples are provided to demonstrate the effectiveness of the approaches we consider herein.
We study the two-user multiple-input single-output (MISO) Gaussian interference channel where the transmitters have perfect channel state information and employ single-stream beamforming. The receivers are capable of performing successive interference cancellation, so when the interfering signal is strong enough, it can be decoded, treating the desired signal as noise, and subtracted from the received signal, before the desired signal is decoded. We propose efficient methods to compute the Pareto-optimal rate points and corresponding beamforming vector pairs, by maximizing the rate of one link given the rate of the other link. We do so by splitting the original problem into four subproblems corresponding to the combinations of the receivers' decoding strategies-either decode the interference or treat it as additive noise. We utilize recently proposed parameterizations of the optimal beamforming vectors to equivalently reformulate each subproblem as a quasi-concave problem, which we solve very efficiently either analytically or via scalar numerical optimization. The computational complexity of the proposed methods is several orders-of-magnitude less than the complexity of the state-of-the-art methods. We use the proposed methods to illustrate the effect of the strength and spatial correlation of the channels on the shape of the rate region.
Traditional maximum entropy spectral estimation determines a power spectrum from covariance estimates. Here, we present a new approach to spectral estimation, which is based on the use of filter banks as a means of obtaining spectral interpolation data, Such data replaces standard covariance estimates, A computational procedure for obtaining suitable pole-zero (ARMA) models from such data is presented. The choice of the zeros (MA-part) of the model is completely arbitrary. By suitably choices of filterbank poles and spectral zeros, the estimator can be tuned to exhibit high resolution in targeted regions of the spectrum.
Space-time coding has been receiving much attention due to its potentials offered by fully exploiting the spatial and temporal diversities of multiple transmit and receive antennas. A differential space-time modulation (DSTM) scheme was previously proposed for demodulation without channel state information, which is attractive in fast fading channels where accurate channel estimates are difficult to obtain. However, this technique is sensitive to interference and is likely to deteriorate or even break down in a wireless environment, where interference (including intentional and unintentional jamming) signals exist. We propose a new coding and modulation scheme, referred to as the differential space-code modulation (DSCM), which is interference resistant. Our focus is on single-user communications. We show that DSCM outperforms DSTM significantly when interference is present. This advantage is achieved at the cost of a lower data rate or a wider bandwidth or a combination of both. To alleviate this problem, a high-rate DSCM (HR-DSCM) scheme is also presented, which increases the data rate considerably at the cost of a slightly higher bit-error rate (BER), while still maintaining the interference suppression capability.
We address high-level synthesis of low-power digital signal processing (DSP) systems by using efficient switching activity models. We present a technology-independent hierarchical scheme that can be easily integrated into current communications/DSP CAD tools for comparing the relative power/performance of two competing DSP designs without specific knowledge of transistor-level details. The basic building blocks considered for such systems are a full adder, a half adder, and a one-bit delay. Estimates of the switching activity at the output of these primitives are used to model the activity in more complex building blocks of DSP systems. The presented hierarchical method is very fast and simple. The accuracy of estimates obtained using the proposed approach is shown to be within 4% of the results obtained using extensive bit-level simulations. Our approach shows that the choice of multiplier/multiplicand is important when using array multipliers in a datapath. If the input signal with smaller mean square value is chosen as the multiplicand, almost 20% savings in switching activity can be achieved. This observation is verified by an analog simulation using a 16 × 16 bit array multiplier implemented in a 0.6-μ process with 3.3 V supply voltage.
Signal processing methods for digital post-correction of analog-to-digital converters (ADCs) are, considered. ADC errors are in general signal dependent, and in addition, they often exhibit dynamic dependence. A novel dynamic post-correction scheme based on look-up tables is proposed. In order to reduce the table size and, thus, the hardware requirements, bit-masking is, introduced. This. is to limit the length of the table index by deselecting index bits. At this point, the problem of which bits to use arises. A mathematical analysis tool is derived, enabling the allocation of index bits to be analyzed. This analysis tool is applied in two optimization problems, optimizing the total harmonic distortion and the signal-to-noise and distortion ratio, respectively, of a corrected ADC. The correction scheme and the optimization problems are illustrated and exemplified using experimental ADC data. The results show that the proposed correction scheme improves the performance of the ADC. They also indicate that the allocation of index bits has a significant impact on the ADC performance, motivating the analysis tool. Finally, the optimization results show that performance improvements compared with static look-up table correction can be achieved, even at a comparable table size.
Mapping stationary objects is essential for autonomous vehicles and many autonomous functions in vehicles. In this contribution the probability hypothesis density (PHD) filter framework is applied to automotive imagery sensor data for constructing such a map, where the main advantages are that it avoids the detection, the data association and the track handling problems in conventional multiple-target tracking, and that it gives a parsimonious representation of the map in contrast to grid based methods. Two original contributions address the inherent complexity issues of the algorithm: First, a data clustering algorithm is suggested to group the components of the PHD into different clusters, which structures the description of the prior and considerably improves the measurement update in the PHD filter. Second, a merging step is proposed to simplify the map representation in the PHD filter. The algorithm is applied to multi-sensor radar data collected on public roads, and the resulting map is shown to well describe the environment as a human perceives it.
This paper presents an extended target tracking framework which uses polynomials in order to model extended objects in the scene of interest from imagery sensor data. State-space models are proposed for the extended objects which enables the use of Kalman filters in tracking. Different methodologies of designing measurement equations are investigated. A general target tracking algorithm that utilizes a specific data association method for the extended targets is presented. The overall algorithm must always use some form of prior information in order to detect and initialize extended tracks from the point tracks in the scene. This aspect of the problem is illustrated on a real life example of road-map estimation from automotive radar reports along with the results of the study.
The conventional memory organization of fast Fourier transform (FFT) processors is based on Cohen's scheme, Compared Kith this scheme, our scheme reduces the hardware complexity of address generation by about 50% while improving the memory access speed, Much power consumption in memory is saved since only half of the memory is activated during memory access, and the number of coefficient access is reduced to a minimum by using a nem ordering of FFT butterflies. Therefore, the new scheme is a superior solution to constructing high-performance FFT processors.
In distributed optimization and machine learning, multiple nodes coordinate to solve large problems. To do this, the nodes need to compress important algorithm information to bits so that it can be communicated over a digital channel. The communication time of these algorithms follows a complex interplay between a) the algorithm's convergence properties, b) the compression scheme, and c) the transmission rate offered by the digital channel. We explore these relationships for a general class of linearly convergent distributed algorithms. In particular, we illustrate how to design quantizers for these algorithms that compress the communicated information to a few bits while still preserving the linear convergence. Moreover, we characterize the communication time of these algorithms as a function of the available transmission rate. We illustrate our results on learning algorithms using different communication structures, such as decentralized algorithms where a single master coordinates information from many workers and fully distributed algorithms where only neighbours in a communication graph can communicate. We conclude that a co-design of machine learning and communication protocols are mandatory to flourish machine learning over networks.
This paper introduces an efficient algorithm for finding the dominant generalized eigenvectors of a pair of symmetric matrices. Combining tools from approximation theory and convex optimization, we develop a simple scalable algorithm with strong theoretical performance guarantees. More precisely, the algorithm retains the simplicity of the well-knownpower method but enjoys the asymptotic iteration complexity of the powerful Lanczos method. Unlike these classic techniques, our algorithm is designed to decompose the overall problem into a series of subproblems that only need to be solved approximately. The combination of good initializations, fast iterative solvers, and appropriate error control in solving the subproblems lead to a linear running time in the input sizes compared to the superlinear time for the traditional methods. The improved running time immediately offers acceleration for several applications. As an example, we demonstrate how the proposed algorithm can be used to accelerate canonical correlation analysis, which is a fundamental statistical tool for learning of a low-dimensional representation of high-dimensional objects. Numerical experiments on real-world datasets confirm that our approach yields significant improvements over the current state of the art.
l1 mean filtering is a conventional, optimizationbasedmethod to estimate the positions of jumps in a piecewiseconstant signal perturbed by additive noise. In this method, the l1 norm penalizes sparsity of the first-order derivative of the signal.Theoretical results, however, show that in some situations, whichcan occur frequently in practice, even when the jump amplitudes tend to , the conventional method identifies false change points.This issue is referred to as stair-casing problem in this paper andrestricts practical importance of l1 mean filtering. In this paper, sparsity is penalized more tightly than the l1 norm by exploiting a certain class of nonconvex functions, while the strict convexity ofthe consequent optimization problem is preserved. This results in a higher performance in detecting change points. To theoretically justify the performance improvements over l1 mean filtering, deterministic and stochastic sufficient conditions for exact changepoint recovery are derived. In particular, theoretical results show that in the stair-casing problem, our approach might be able to exclude the false change points, while l1 mean filtering may fail. A number of numerical simulations assist to show superiorityof our method over l1 mean filtering and another state-of-theart algorithm that promotes sparsity tighter than the l1 norm. Specifically, it is shown that our approach can consistently detectchange points when the jump amplitudes become sufficiently large, while the two other competitors cannot.
In this paper, the problem of matrix rank minimization under affine constraints is addressed. The state-of-the-art algorithms can recover matrices with a rank much less than what is sufficient for the uniqueness of the solution of this optimization problem. We propose an algorithm based on a smooth approximation of the rank function, which practically improves recovery limits on the rank of the solution. This approximation leads to a non-convex program; thus, to avoid getting trapped in local solutions, we use the following scheme. Initially, a rough approximation of the rank function subject to the affine constraints is optimized. As the algorithm proceeds, finer approximations of the rank are optimized and the solver is initialized with the solution of the previous approximation until reaching the desired accuracy. On the theoretical side, benefiting from the spherical section property, we will show that the sequence of the solutions of the approximating programs converges to the minimum rank solution. On the experimental side, it will be shown that the proposed algorithm, termed SRF standing for smoothed rank function, can recover matrices, which are unique solutions of the rank minimization problem and yet not recoverable by nuclear norm minimization. Furthermore, it will be demonstrated that, in completing partially observed matrices, the accuracy of SRF is considerably and consistently better than some famous algorithms when the number of revealed entries is close to the minimum number of parameters that uniquely represent a low-rank matrix.
In this paper, we propose a new algorithm for recovery of low-rank matrices from compressed linear measurements. The underlying idea of this algorithm is to closely approximate the rank function with a smooth function of singular values, and then minimize the resulting approximation subject to the linear constraints. The accuracy of the approximation is controlled via a scaling parameter δ, where a smaller δ corresponds to a more accurate fitting. The consequent optimization problem for any finite δ is nonconvex. Therefore, to decrease the risk of ending up in local minima, a series of optimizations is performed, starting with optimizing a rough approximation (a large δ) and followed by successively optimizing finer approximations of the rank with smaller δ's. To solve the optimization problem for any δ > 0, it is converted to a new program in which the cost is a function of two auxiliary positive semidefinite variables. The paper shows that this new program is concave and applies a majorize-minimize technique to solve it which, in turn, leads to a few convex optimization iterations. This optimization scheme is also equivalent to a reweighted Nuclear Norm Minimization (NNM). For any δ > 0, we derive a necessary and sufficient condition for the exact recovery which are weaker than those corresponding to NNM. On the numerical side, the proposed algorithm is compared to NNM and a reweighted NNM in solving affine rank minimization and matrix completion problems showing its considerable and consistent superiority in terms of success rate.
In this paper, based on a successively accuracy-increasing approximation of the l(0) norm, we propose a new algorithm for recovery of sparse vectors from underdetermined measurements. The approximations are realized with a certain class of concave functions that aggressively induce sparsity and their closeness to the l(0) norm can be controlled. We prove that the series of the approximations asymptotically coincides with the l(1) and l(0) norms when the approximation accuracy changes from the worst fitting to the best fitting. When measurements are noise-free, an optimization scheme is proposed that leads to a number of weighted l(1) minimization programs, whereas, in the presence of noise, we propose two iterative thresholding methods that are computationally appealing. A convergence guarantee for the iterative thresholding method is provided, and, for a particular function in the class of the approximating functions, we derive the closed-form thresholding operator. We further present some theoretical analyses via the restricted isometry, null space, and spherical section properties. Our extensive numerical simulations indicate that the proposed algorithm closely follows the performance of the oracle estimator for a range of sparsity levels wider than those of the state-of-the-art algorithms.
A parameter estimation method for finite dimensional multivariate linear stochastic systems, which is guaranteed to produce valid models approximating the true underlying system in a computational time of a polynomial order in the system dimension, is presented. This is achieved by combining the main features of certain stochastic subspace identification techniques with sound matrix Schur restabilizing procedures and multivariate covariance fitting, both of which are formulated as linear matrix inequality problems. all aspects of the identification method are discussed, with an emphasis on the two issues mentioned above, and examples of the overall performance are provided for two different systems.
Bayesian filtering deals with computing the posterior distribution of the state of a stochastic dynamic system given noisy observations. In this paper, motivated by applications in counter-adversarial autonomous systems, we consider the following inverse filtering problem: Given a sequence of posterior distributions from a Bayesian filter, what can be inferred about the transition kernel of the state, the observation likelihoods of the sensor and the measured observations? For finite-state Markov chains observed in noise (hidden Markov models), we show that a least-squares fit for estimating the parameters and observations amounts to a combinatorial optimization problem with non-convex objective. Instead, by exploiting the algebraic structure of the corresponding Bayesian filter, we propose an algorithm based on convex optimization for reconstructing the transition kernel, the observation likelihoods and the observations. We discuss and derive conditions for identifiability. As an application of our results, we demonstrate the design of a counter-adversarial autonomous system: By observing the actions of an autonomous enemy, we estimate the accuracy of its sensors and the observations it has received. The proposed algorithms are illustrated via several numerical examples.
The linear minimum mean-square error estimator (LMMSE) can be viewed as a solution to a certain regularized least-squares problem formulated using model covariance matrices. However, the appropriate parameters of the model covariance matrices are unknown in many applications. This raises the question: how should we choose them using only the data? Using data-adaptive matrices obtained via the covariance fitting SPICE-methodology, we show that the empirical LMMSE is equivalent to tuned versions of various known regularized estimators - such as ridge regression, LASSO, and regularized least absolute deviation - depending on the chosen covariance structures. These theoretical results unify several important estimators under a common umbrella. Furthermore, through a number of numerical examples we show that the regularization parameters obtained via covariance fitting are close to optimal for a range of different signal conditions.
We consider the downlink of a multiuser system with multiple antennas at the base station. Vector perturbation (VP) precoding is a promising variant of transmit-side channel inversion allowing the users to detect their data in a simple, noncooperative manner. VP precoding has so far been developed and analyzed under the assumptions that the transmitter has perfect channel state information (CSI) and that the receivers know perfectly a channel-dependent transmit power normalization factor and have infinite dynamic range. We demonstrate that the violation of any of these idealizing assumptions degrades the performance of VP significantly and almost always results in an error floor. Motivated by this observation, we propose a novel scheme which we term transmit outage precoding (TOP). With TOP, the transmitter uses a prearranged power scaling known by the receivers and refrains from transmitting when channel conditions are poor. We further show how to augment TOP and conventional VP to deal with a finite dynamic range at the receiver. The performance of the proposed schemes under various levels of transmit CSI is studied in terms of a theoretical diversity analysis and illustrated by numerical results.
The parameter estimation of moving-average (MA) signals from second-order statistics was deemed for a long time to be a difficult nonlinear problem for which no computationally convenient and reliable solution was possible. We show how the problem of MA parameter estimation from sample covariances can be formulated as a semidefinite program that can be solved in a time that is a polynomial function of the MA order. Two methods are proposed that rely on two specific (over) parametrizations of the MA covariance sequence, whose use makes the minimization of a covariance fitting criterion a convex problem. The MA estimation algorithms proposed here are computationally fast, statistically accurate, and reliable. None of the previously available algorithms for MA estimation (methods based on higher-order statistics included) shares all these desirable properties. Our methods can also be used to obtain the optimal least squares approximant of an invalid (estimated) MA spectrum (that takes on negative values at some frequencies), which was another long-standing problem in the signal processing literature awaiting a satisfactory solution.