Diffusion models deliver state-of-the-art generative performance across diverse modalities but remain computationally expensive due to their inherently iterative sampling process. Existing training-free acceleration methods typically improve numerical solvers for the reverse-time ODE, yet their effectiveness is fundamentally constrained by the inefficiency of the underlying sampling trajectories. We propose A-FloPS (Adaptive Flow Path Sampler), a principled, training-free framework that reparameterizes the sampling trajectory of any pre-trained diffusion model into a flow-matching form and augments it with an adaptive velocity decomposition. The reparameterization analytically maps diffusion scores to flow-compatible velocities, yielding integration-friendly trajectories without retraining. The adaptive mechanism further factorizes the velocity field into a linear drift term and a residual component whose temporal variation is actively suppressed, restoring the accuracy benefits of high-order integration even in extremely low-NFE regimes. Extensive experiments on conditional image generation and text-to-image synthesis show that A-FloPS consistently outperforms state-of-the-art training-free samplers in both sample quality and efficiency. Notably, with as few as 5 function evaluations, A-FloPS achieves substantially lower FID and generates sharper, more coherent images. The adaptive mechanism also improves native flow-based generative models, underscoring its generality. These results position A-FloPS as a versatile and effective solution for high-quality, low-latency generative modeling.

Time Series Anomaly Detection (TSAD) methods often require large datasets and extensive domain knowledge, limiting their effectiveness in data-scarce environments. We introduce a novel unsupervised TSAD approach based on path signatures, which efficiently extracts shape features from time series data without requiring additional parameters. By leveraging multi-scale signature feature extraction, our method achieves faster inference and higher performance compared to deep learning models, as demonstrated on multiple cross-domain datasets. Experimental results confirm the strong generalization capability and computational efficiency of our approach.

Classifier-free guidance (CFG) has emerged as a pivotal advancement in text-to-image latent diffusion models, establishing itself as a cornerstone technique for achieving high-quality image synthesis. However, under high guidance weights, where text-image alignment is significantly enhanced, CFG also leads to pronounced color distortions in the generated images. We identify that these distortions stem from the amplification of sample norms in the latent space. We present a theoretical framework that elucidates the mechanisms of norm amplification and anomalous diffusion phenomena induced by classifier-free guidance. Leveraging our theoretical insights and the latent space structure, we propose an Angle Domain Guidance (ADG) algorithm. ADG constrains magnitude variations while optimizing angular alignment, thereby mitigating color distortions while preserving the enhanced text-image alignment achieved at higher guidance weights. Experimental results demonstrate that ADG significantly outperforms existing methods, generating images that not only maintain superior text alignment but also exhibit improved color fidelity and better alignment with human perceptual preferences.

We present Open-CD, a change detection toolbox that contains a rich set of change detection methods as well as related components and modules. The toolbox started from a series of open source general vision task tools, including OpenMMLab Toolkits, PyTorch Image Models (Timm), etc. It gradually evolves into a unified platform that covers many popular change detection methods and contemporary modules. It not only includes training and inference codes, but also provides some useful scripts for data analysis. We believe this toolbox is by far the most comprehensive change detection toolbox. In this report, we introduce the features, supported methods and applications of Open-CD. In addition, we also conduct a benchmarking study on different methods and components. We wish that the toolbox and benchmark could serve the growing research community by providing a flexible toolkit to re-implement existing methods and develop their own new change detectors. Code and models are available at https://github.com/likyoo/open-cd.

Diffusion-based inverse algorithms have shown remarkable performance across various inverse problems, yet their reliance on numerous denoising steps incurs high computational costs. While recent developments of fast diffusion ODE solvers offer effective acceleration for diffusion sampling without observations, their application in inverse problems remains limited due to the heterogeneous formulations of inverse algorithms and their prevalent use of approximations and heuristics, which often introduce significant errors that undermine the reliability of analytical solvers. In this work, we begin with an analysis of ODE solvers for inverse problems that reveals a linear combination structure of approximations for the inverse trajectory. Building on this insight, we propose a canonical form that unifies a broad class of diffusion-based inverse algorithms and facilitates the design of more generalizable solvers. Inspired by the linear subspace search strategy, we propose Learnable Linear Extrapolation (LLE), a lightweight approach that universally enhances the performance of any diffusion-based inverse algorithm conforming to our canonical form. LLE optimizes the combination coefficients to refine current predictions using previous estimates, alleviating the sensitivity of analytical solvers for inverse algorithms. Extensive experiments demonstrate consistent improvements of the proposed LLE method across multiple algorithms and tasks, indicating its potential for more efficient solutions and boosted performance of diffusion-based inverse algorithms with limited steps. Codes for reproducing our experiments are available at https://github.com/weigerzan/LLE_inverse_problem.

Most existing change detection (CD) methods focus on optical images captured at different times, and deep learning (DL) has achieved remarkable success in this domain. However, in extreme scenarios such as disaster response, synthetic aperture radar (SAR), with its active imaging capability, is more suitable for providing post-event data. This introduces new challenges for CD methods, as existing weight-sharing Siamese networks struggle to effectively learn the cross-modal data distribution between optical and SAR images. To address this challenge, we propose a unified MultiModal CD framework, M2CD. We integrate Mixture of Experts (MoE) modules into the backbone to explicitly handle diverse modalities, thereby enhancing the model’s ability to learn multimodal data distributions. Additionally, we innovatively propose an Optical-to-SAR path (O2SP) and implement self-distillation during training to reduce the feature space discrepancy between different modalities, further alleviating the model’s learning burden. We design multiple variants of M2CD based on both CNN and Transformer backbones. Extensive experiments validate the effectiveness of the proposed framework, with the MiT-b1 version of M2CD outperforming all state-of-the-art (SOTA) methods in optical-SAR CD tasks. Code is available at https://github.com/circleLZY/M2CD.

In this paper, we study the deep learning (DL) based channel extrapolation problem and conduct the over-the-air (OTA) antenna extrapolation and frequency channel interpolation test for the 3rd generation partnership project (3GPP) long-term evolution (LTE) time-division duplex (TDD)-like orthogonal frequency division multiplexing (OFDM) massive MIMO prototype. We first present measurement campaigns using universal software radio peripherals (USRP) at 3.5 GHz, where the base station (BS) is composed of a 64-element antenna array. A DL-based antenna extrapolation network is then designed to approximate the inner deterministic function among antennas from the attained channel data within the “training” pilots. We present an antenna selection network (ASN) that can select a limited number of antennas for the best extrapolation, which outperforms the uniform antenna selection in terms of channel reconstruction and signal detection. We also design a deep residual neural network for channel interpolation. The performance of the extrapolated channel is evaluated in terms of normalized mean squared error (NMSE) in comparison to the measured channels on all antenna ports or the full pilot-aided channels in all OFDM subcarriers. Experimental results show that ASN can reduce an average of 87.5% antenna ports and maintain channel estimation NMSE by$10^{-2}$when compared to 3GPP channel estimation protocols.

Out-of-distribution (OOD) detection plays a crucial role in ensuring the security of neural networks. Existing works have leveraged the fact that In-distribution (ID) samples form a subspace in the feature space, achieving state-of-the-art (SOTA) performance. However, the comprehensive characteristics of the ID subspace still leave underexplored. Recently, the discovery of Neural Collapse $\left( {\mathcal{N}\mathcal{C}} \right)$ sheds light on novel properties of the ID subspace. Leveraging insight from $\mathcal{N}\mathcal{C}$, we observe that the Principal Angle between the features and the ID feature subspace forms a superior representation for measuring the likelihood of OOD. Building upon this observation, we propose a novel $\mathcal{N}\mathcal{C}$-inspired OOD scoring function, named Entropy-enhanced Principal Angle (EPA), which integrates both the global characteristic of the ID subspace and its inner property. We experimentally compare EPA with various SOTA approaches, validating its superior performance and robustness across different network architectures and OOD datasets.

Traditional Time-series Anomaly Detection (TAD) methods often struggle with the composite nature of complex time-series data and a diverse array of anomalies. We introduce TADNet, an end-to-end TAD model that leverages Seasonal-Trend Decomposition to link various types of anomalies to specific decomposition components, thereby simplifying the analysis of complex time-series and enhancing detection performance. Our training methodology, which includes pre-training on a synthetic dataset followed by fine-tuning, strikes a balance between effective decomposition and precise anomaly detection. Experimental validation on real-world datasets confirms TADNet’s state-of-the-art performance across a diverse range of anomalies.

The recent emergence of diffusion models has significantly advanced the precision of learnable priors, presenting innovative avenues for addressing inverse problems. Previous works have endeavored to integrate diffusion priors into the maximum a posteriori estimation (MAP) framework and design optimization methods to solve the inverse problem. However, prevailing optimization-based rithms primarily exploit the prior information within the diffusion models while neglecting their denoising capability. To bridge this gap, this work leverages the diffusion process to reframe noisy inverse problems as a two-variable constrained optimization task by introducing an auxiliary optimization variable that represents a 'noisy' sample at an equivalent denoising step. The projection gradient descent method is efficiently utilized to solve the corresponding optimization problem by truncating the gradient through the $\mu$-predictor. The proposed algorithm, termed ProjDiff, effectively harnesses the prior information and the denoising capability of a pre-trained diffusion model within the optimization framework. Extensive experiments on the image restoration tasks and source separation and partial generation tasks demonstrate that ProjDiff exhibits superior performance across various linear and nonlinear inverse problems, highlighting its potential for practical applications. Code is available at https://github.com/weigerzan/ProjDiff/.

In this paper, we investigate the correlation between the sub-6GHz channel and the millimeter wave (mmWave) chan-nel, and then predict the mmWave downlink hybrid beamforming (HBF) matrices directly from the sub-6GHz uplink channel, based on a sophisticatedly designed deep learning architecture. Specifically, the neural network structure consists of three functional modules: the feature extraction module extracts channel features from a large amount of channel data, the feature fusion module combines multidimensional features, and the prediction module generates the HBF matrix. Moreover, we develop a power constraint module for digital domain and a constant modulus constraint module for analog domain to ensure that the output of the network satisfies the characteristics of HBF. Simulation results show that the proposed sub-6GHz assisted HBF algorithm without mmWave channel estimation saves 75% of channel state information compared to the method using mmWave pilot resources directly. Furthermore, to facilitate deployment, we design a low-complexity structure that achieves a remarkable reduction of 98.52% in parameters and 22.93% in computations.

In the burgeoning ecosystem of Internet of Things, multivariate time series (MTS) data has become ubiquitous, highlighting the fundamental role of time series forecasting across numerous applications. The crucial challenge of long-term MTS forecasting requires adept models capable of capturing both intra-and inter-series dependencies. Recent advancements in deep learning, notably Transformers, have shown promise. However, many prevailing methods either marginalize inter-series dependencies or overlook them entirely. To bridge this gap, this paper introduces a novel series-aware framework, explicitly designed to emphasize the significance of such dependencies. At the heart of this framework lies our specific implementation: the SageFormer. As a Series-aware Graph-enhanced Transformer model, SageFormer proficiently discerns and models the intricate relationships between series using graph structures. Beyond capturing diverse temporal patterns, it also curtails redundant information across series. Notably, the series-aware framework seamlessly integrates with existing Transformer-based models, enriching their ability to comprehend inter-series relationships. Extensive experiments on real-world and synthetic datasets validate the superior performance of SageFormer against contemporary state-of-the-art approaches.

Due to its inherent characteristics, the synthetic aperture radar (SAR) image is mainly corrupted by speckle noise, posing additional challenges to lossy image compression algorithms. Traditional optical image compression techniques lack the ability to distinguish between image details and noise, which increases storage costs and restores images that still contain noise. Inspired by these observations, we optimize image compression algorithms to incorporate denoising capabilities, enabling joint denoising and compression of SAR images. Specifically, we transform the raw speckled images into noise-free bitstreams, allowing the subsequent decompression to produce clean images. To achieve this objective efficiently, we introduce a novel knowledge distillation strategy that incurs no additional computational cost. Furthermore, this distillation mechanism yields statistically significant performance improvements across various image compression algorithms. Experimental results demonstrate that when evaluated on both synthetic and real-world datasets, the proposed method not only achieves the best visual effects but also outperforms existing methods in terms of rate-distortion performance, equivalent number of looks, and other quantitative indicators.

Deep learning has achieved success in optical image super-resolution (SR). However, few methods have been proposed for synthetic aperture radar (SAR) images. This is because SAR images inherently suffer from severe speckle noise, and their resolution is typically much lower compared with optical images, making SR more challenging. To simultaneously denoise and preserve texture details in SAR image SR tasks, we propose a joint despeckling and SR network via knowledge distillation (DSRKD). By implementing feature distillation (FD) in the encoding stage, we enable the student network to obtain noise-free latent variables, thereby restoring clean SR images, and simultaneously enhancing effective supervision for the student using target distillation (TD). This distillation strategy does not incur additional computational costs during inference. Experimental results demonstrate that our algorithm effectively suppresses speckle noise while preserving texture details of images on both synthetic and SAR datasets. Compared with other state-of-the-art algorithms, the proposed method achieves superior performance on both visual results and quantitative metrics, such as PSNR, SSIM, and other nonreference indicators under various SR scales and speckle intensities.

We study the problem of reconstructing a continuous multidimensional signal from a small number of samples under Fourier constraints assuming that the Fourier power spectrum of the signal has some desirable properties, e.g. being compactly supported, being sparse. We further assume that the Fourier constraint can be expressed as a prior distribution on the Fourier power spectrum, which subsumes the aforementioned examples. The study of sampling and reconstructing in this vein has attracted much attention with a long history. In this paper, we are interested in finding oblivious sampling strategies, that is, sampling without knowing what specific constraint is put on the Fourier power spectrum. We show that it is possible to obliviously sample a Fourier-constrained multidimensional signal with a near-optimal (up to a logarithmic factor) number of samples that guarantee successful reconstruction, partially answering an open question in Avron et al. (2019) which considered the $1$-dimensional case. Our approach highlights a phenomenon that is unique for dimension $d\ge 2$ that the sampling strategy should depend on the geometry of the region on which the signal is to be reconstructed, unlike the case $d=1$ where all regions are of the form $[a,b]$ which are all geometrically equivalent. Our proof, using tools from convex geometry, also illuminates an idea obscured in $d=1$, that to reconstruct a signal in a given region, it can be helpful to take some samples outside that region.

Benign overfitting refers to a recently discovered intriguing phenomenon that over-parameterized neural networks, in many cases, can fit the training data perfectly but still generalize well, surprisingly contrary to the traditional belief that overfitting is harmful for generalization. In spite of its surging popularity in recent years, little has been known in the theoretical aspect of benign overfitting of neural networks. In this work, we provide a theoretical analysis of benign overfitting for two-layer neural networks with possibly non-smooth activation function. Without resorting to the popular Neural Tangent Kernel (NTK) approximation, we prove that neural networks can be trained with gradient descent to classify binary-labeled training data perfectly (achieving zero training loss) even in presence of polluted labels, but still generalize well. Our result removes the smoothness assumption in previous literature and goes beyond the NTK regime; this enables a better theoretical understanding of benign overfitting within a practically more meaningful setting, e.g., with (leaky-)ReLU activation function, small random initialization, and finite network width.

We consider the problem of distributed principal component analysis (PCA) where the data samples are dispersed across different agents. Despite the rich literature on this problem under various specific settings, there is still a lack of efficient algorithms that are amenable to decentralized and asynchronous implementations. In this paper, we extend the incremental aggregated gradient (IAG) method in convex optimization to the nonconvex PCA problems based on an Riemannian gradient-type method named IARG-PCA. The IARG-PCA method admits low per-iteration computational and communication cost and can be readily implemented in a decentralized and asynchronous manner. Moreover, we show that the IARG-PCA method converges linearly to the leading eigenvector of the sample covariance of the whole dataset with a constant step size. The iteration complexity coincides with the best-known result of the IAG method in terms of the linear dependence on the number of agents. Meanwhile, the communication complexity is much lower than the state-of-the-art decentralized PCA algorithms if the eigengap of the sample covariance is moderate. Numerical experiments on synthetic and real datasets show that our IARG-PCA method exhibits substantially lower communication cost and comparable computational cost compared with other existing algorithms.

Unlocking the potential of deep learning in Peak-Hour Series Forecasting (PHSF) remains a critical yet underexplored task in various domains. While state-of-the-art deep learning models excel in regular Time Series Forecasting (TSF), they struggle to achieve comparable results in PHSF. This can be attributed to the challenges posed by the high degree of non-stationarity in peak-hour series, which makes direct forecasting more difficult than standard TSF. Additionally, manually extracting the maximum value from regular forecasting results leads to suboptimal performance due to models minimizing the mean deficit. To address these issues, this paper presents Seq2Peak, a novel framework designed specifically for PHSF tasks, bridging the performance gap observed in TSF models. Seq2Peak offers two key components: the CyclicNorm pipeline to mitigate the non-stationarity issue and a simple yet effective trainable-parameter-free peak-hour decoder with a hybrid loss function that utilizes both the original series and peak-hour series as supervised signals. Extensive experimentation on publicly available time series datasets demonstrates the effectiveness of the proposed framework, yielding a remarkable average relative improvement of 37.7% across four real-world datasets for both transformer- and non-transformer-based TSF models.

A crucial problem of neural networks is to select an architecture that strikes appropriate tradeoffs between underfitting and overfitting. This work shows that$\ell _1$regularizations for two-layer neural networks can control the generalization error and sparsify the input dimension. In particular, with an appropriate$\ell _1$regularization on the output layer, the network can produce a tight statistical risk. Moreover, an appropriate$\ell _1$regularization on the input layer leads to a risk bound that does not involve the input data dimension. The results also indicate that training a wide neural network with a suitable regularization provides an alternative bias-variance tradeoff to selecting from a candidate set of neural networks. Our analysis is based on a new integration of dimension-based and norm-based complexity analysis to bound the generalization error.

In this letter, we present a differentially private algorithm which accurately estimates the mean of an underlying population with given cumulative distribution function. Our algorithm outperforms the former algorithms in two aspects. First, our algorithm is capably of handling more general types of probability distributions, possibly with a very heavy tail. Second, for light-tailed distributions, our algorithm achieves a better level of accuracy with fewer samples.

Asynchronous Q-learning aims to learn the optimal action-value function (or Q-function) of a Markov decision process (MDP), based on a single trajectory of Markovian samples induced by a behavior policy. Focusing on a$\gamma $-discounted MDP with state space$\mathcal {S}$and action space$\mathcal {A}$, we demonstrate that the$\ell _{\infty }$-based sample complexity of classical asynchronous Q-learning — namely, the number of samples needed to yield an entrywise$\varepsilon $-accurate estimate of the Q-function — is at most on the order of$\frac {1}{ \mu _{\mathsf {min}}(1-\gamma)^{5}\varepsilon ^{2}}+ \frac { t_{\mathsf {mix}}}{ \mu _{\mathsf {min}}(1-\gamma)}$up to some logarithmic factor, provided that a proper constant learning rate is adopted. Here,$t_{\mathsf {mix}}$and$\mu _{\mathsf {min}}$denote respectively the mixing time and the minimum state-action occupancy probability of the sample trajectory. The first term of this bound matches the sample complexity in the synchronous case with independent samples drawn from the stationary distribution of the trajectory. The second term reflects the cost taken for the empirical distribution of the Markovian trajectory to reach a steady state, which is incurred at the very beginning and becomes amortized as the algorithm runs. Encouragingly, the above bound improves upon the state-of-the-art result by a factor of at least$|\mathcal {S}||\mathcal {A}|$for all scenarios, and by a factor of at least$t_{\mathsf {mix}}|\mathcal {S}||\mathcal {A}|$for any sufficiently small accuracy level$\varepsilon $. Further, we demonstrate that the scaling on the effective horizon$\frac {1}{1-\gamma }$can be improved by means of variance reduction.

The softmax policy gradient (PG) method, which performs gradient ascent under softmax policy parameterization, is arguably one of the de facto implementations of policy optimization in modern reinforcement learning. For $\gamma$-discounted infinite-horizon tabular Markov decision processes (MDPs), remarkable progress has recently been achieved towards establishing global convergence of softmax PG methods in finding a near-optimal policy. However, prior results fall short of delineating clear dependencies of convergence rates on salient parameters such as the cardinality of the state space $\mathcal{S}$ and the effective horizon $\frac{1}{1-\gamma}$, both of which could be excessively large. In this paper, we deliver a pessimistic message regarding the iteration complexity of softmax PG methods, despite assuming access to exact gradient computation. Specifically, we demonstrate that the softmax PG method with stepsize $\eta$ can take \[ \frac{1}{\eta} |\mathcal{S}|^{2^{\Omega\big(\frac{1}{1-\gamma}\big)}} \text{iterations} \]{to} converge, even in the presence of a benign policy initialization and an initial state distribution amenable to exploration (so that the distribution mismatch coefficient is not exceedingly large). This is accomplished by characterizing the algorithmic dynamics over a carefully-constructed MDP containing only three actions. Our exponential lower bound hints at the necessity of carefully adjusting update rules or enforcing proper regularization in accelerating PG methods.

Q-learning, which seeks to learn the optimal Q-function of a Markov decision process (MDP) in a model-free fashion, lies at the heart of reinforcement learning. Focusing on the synchronous setting (such that independent samples for all state-action pairs are queried via a generative model in each iteration), substantial progress has been made recently towards understanding the sample efficiency of Q-learning. To yield an entrywise $\varepsilon$-accurate estimate of the optimal Q-function, state-of-the-art theory requires at least an order of $\frac{|S||A|}{(1-\gamma)^5\varepsilon^{2}}$ samples in the infinite-horizon $\gamma$-discounted setting. In this work, we sharpen the sample complexity of synchronous Q-learning to the order of $\frac{|S||A|}{(1-\gamma)^4\varepsilon^2}$ (up to some logarithmic factor) for any $0<\varepsilon <1$, leading to an order-wise improvement in $\frac{1}{1-\gamma}$. Analogous results are derived for finite-horizon MDPs as well. Notably, our sample complexity analysis unveils the effectiveness of vanilla Q-learning, which matches that of speedy Q-learning without requiring extra computation and storage. Our result is obtained by identifying novel error decompositions and recursion relations, which might shed light on how to study other variants of Q-learning.

Spectral method is a commonly used scheme to cluster data points lying close to Union of Subspaces, a task known as Subspace Clustering. The typical usage is to construct a Random Geometry Graph first and then apply spectral method to the graph to obtain clustering result. The latter step has been coined the name Spectral Clustering. As far as we know, in spite of the significance of both steps in spectral-method-based Subspace Clustering, all existing theoretical results focus on the first step of constructing the graph, but ignore the final step to correct false connections through spectral clustering. This paper establishes a theory to show the power of this method for the first time, in which we demonstrate the mechanism of spectral clustering by analyzing a simplified algorithm under the widely used semi-random model. Based on this theory, we prove the efficiency of Subspace Clustering in fairly broad conditions. The insights and analysis techniques developed in this paper might also have implications for other random graph problems.

Low-complexity models such as linear function representation play a pivotal role in enabling sample-efficient reinforcement learning (RL). The current paper pertains to a scenario with value-based linear representation, which postulates linear realizability of the optimal Q-function (also called the ``linear $Q^{\star}$ problem''). While linear realizability alone does not allow for sample-efficient solutions in general, the presence of a large sub-optimality gap is a potential game changer, depending on the sampling mechanism in use. Informally, sample efficiency is achievable with a large sub-optimality gap when a generative model is available, but is unfortunately infeasible when we turn to standard online RL settings. We make progress towards understanding this linear $Q^{\star}$ problem by investigating a new sampling protocol, which draws samples in an online/exploratory fashion but allows one to backtrack and revisit previous states. This protocol is more flexible than the standard online RL setting, while being practically relevant and far more restrictive than the generative model. We develop an algorithm tailored to this setting, achieving a sample complexity that scales polynomially with the feature dimension, the horizon, and the inverse sub-optimality gap, but not the size of the state/action space. Our findings underscore the fundamental interplay between sampling protocols and low-complexity function representation in RL.

Achieving sample efficiency in online episodic reinforcement learning (RL) requires optimally balancing exploration and exploitation. When it comes to a finite-horizon episodic Markov decision process with $S$ states, $A$ actions and horizon length $H$, substantial progress has been achieved towards characterizing the minimax-optimal regret, which scales on the order of $\sqrt{H^2SAT}$ (modulo log factors) with $T$ the total number of samples. While several competing solution paradigms have been proposed to minimize regret, they are either memory-inefficient, or fall short of optimality unless the sample size exceeds an enormous threshold (e.g., $S^6A^4 \,\mathrm{poly}(H)$ for existing model-free methods).To overcome such a large sample size barrier to efficient RL, we design a novel model-free algorithm, with space complexity $O(SAH)$, that achieves near-optimal regret as soon as the sample size exceeds the order of $SA\,\mathrm{poly}(H)$. In terms of this sample size requirement (also referred to the initial burn-in cost), our method improves --- by at least a factor of $S^5A^3$ --- upon any prior memory-efficient algorithm that is asymptotically regret-optimal. Leveraging the recently introduced variance reduction strategy (also called {\em reference-advantage decomposition}), the proposed algorithm employs an {\em early-settled} reference update rule, with the aid of two Q-learning sequences with upper and lower confidence bounds. The design principle of our early-settled variance reduction method might be of independent interest to other RL settings that involve intricate exploration-exploitation trade-offs.

Change-point detection (CPD) from streaming data is a fundamental problem in statistical signal processing and has wide applications in wireless sensor networks and the Internet of Things (IoT), such as environmental monitoring and physical activity detection. In various detection schemes, decentralized detection without fusion center is becoming increasingly popular for IoT applications since it enjoys the benefit of strong robustness and security. However, it faces the big challenge of high energy consumption. In this work, we propose an energy-efficient decentralized CPD algorithm called request-response and censoring-based cumulative sum. Specifically, we design a novel communication strategy based on request-response and censoring scheme, which could help the sensors extract useful information from the neighbor sets with a low amount of communication. Furthermore, to provide a guideline on selecting the parameters involved in our algorithm, we theoretically analyze the performance of the proposed algorithm under a simplification for the most interesting cases, in terms of two standard criteria average running length (ARL) and expected detection delay (EDD). Numerical simulations are conducted to verify the effectiveness of the proposed algorithm. Moreover, we test the feasibility of the proposed algorithm in the physical activity CPD task. The experimental results on the real-world data set demonstrate its high energy efficiency and small detection delay.

Multiview subspace clustering, which aims to cluster the given data points with information from multiple sources or features into their underlying subspaces, has a wide range of applications in the communities of data mining and pattern recognition. Compared with the single-view subspace clustering, it is challenging to efficiently learn the structure of the representation matrix from each view and make use of the extra information embedded in multiple views. To address the two problems, a novel correntropy-based multiview subspace clustering (CMVSC) method is proposed in this article. The objective function of our model mainly includes two parts. The first part utilizes the Frobenius norm to efficiently estimate the dense connections between the points lying in the same subspace instead of following the standard compressive sensing approach. In the second part, the correntropy-induced metric (CIM) is introduced to characterize the noise in each view and utilize the information embedded in different views from an information-theoretic perspective. Furthermore, an efficient iterative algorithm based on the half-quadratic technique (HQ) and the alternating direction method of multipliers (ADMM) is developed to optimize the proposed joint learning problem, and extensive experimental results on six real-world multiview benchmarks demonstrate that the proposed methods can outperform several state-of-the-art multiview subspace clustering methods.

To date, most linear and nonlinear Kalman filters (KFs) have been developed under the Gaussian assumption and the well-known minimum mean square error (MMSE) criterion. In order to improve the robustness with respect to impulsive (or heavy-tailed) non-Gaussian noises, the maximum correntropy criterion (MCC) has recently been used to replace the MMSE criterion in developing several robust Kalman-type filters. To deal with more complicated non-Gaussian noises such as noises from multimodal distributions, in this article, we develop a new Kalman-type filter, called minimum error entropy KF (MEE-KF), by using the minimum error entropy (MEE) criterion instead of the MMSE or MCC. Similar to the MCC-based KFs, the proposed filter is also an online algorithm with the recursive process, in which the propagation equations are used to give prior estimates of the state and covariance matrix, and a fixed-point algorithm is used to update the posterior estimates. In addition, the MEE extended KF (MEE-EKF) is also developed for performance improvement in the nonlinear situations. The high accuracy and strong robustness of MEE-KF and MEE-EKF are confirmed by experimental results.

In this work, a distributed non-orthogonal pilot design approach is proposed to tackle the pilot contamination problem in multi-cell massive multiple input multiple output (MIMO) systems. The pilot signals are designed under power constraints by minimizing the total mean square errors (MSEs) of the minimum mean square error (MMSE) channel estimators of all base stations (BSs). In order to solve the above non-convex pilot design problem, the stochastic variance reduced gradient (SVRG) projection algorithm is introduced, where the pilots signals are optimized in a distributed way at individual BSs. The SVRG projection algorithm preserves the randomness of the transient gradient, which makes the solution more likely jump out of the local minima. Moreover, only part of the BSs are activated to perform the gradient descent operation during each iteration, producing a green and low-cost infrastructure. Numerical simulations demonstrate the superiority of the proposed approach in terms of the channel estimation accuracy and uplink achievable sum rate.

Detecting subspace signals is an important problem in radar and sonar signal processing, hyperspectral image processing, wireless communication, and other fields. Among these problems, a typical scenario is that one needs to detect a signal lying in a given target subspace, contaminated by interferences that also lie in some subspaces. Most classical works in this aspect treated only the cases where the interfering subspace is known a priori, but in practice the interfering subspace is often unknown. Recently, the arise of Volume Correlation Detector allows to detect subspace signals when the interfering subspace is unknown, but it does not work well in the case where the target subspace overlaps with the interfering subspace. In this paper, we propose a new detector, called Principal Angle Detector (PAD), based on principal angles between subspaces. Our new detector is robust against overlapping target subspace and interfering subspace, and against some other model mismatches. To provide a correct and reasonable theoretical result, we borrow from the literature of numerical linear algebra the tool of affine-invariant covariance estimation, which could be of potential use for related problems in signal processing.

Asynchronous Q-learning aims to learn the optimal action-value function (or Q-function) of a Markov decision process (MDP), based on a single trajectory of Markovian samples induced by a behavior policy. Focusing on a $\gamma$-discounted MDP with state space S and action space A, we demonstrate that the $ \ell_{\infty} $-based sample complexity of classical asynchronous Q-learning --- namely, the number of samples needed to yield an entrywise $\epsilon$-accurate estimate of the Q-function --- is at most on the order of $ \frac{1}{ \mu_{\min}(1-\gamma)^5 \epsilon^2 }+ \frac{ t_{\mathsf{mix}} }{ \mu_{\min}(1-\gamma) } $ up to some logarithmic factor, provided that a proper constant learning rate is adopted. Here, $ t_{\mathsf{mix}} $ and $ \mu_{\min} $ denote respectively the mixing time and the minimum state-action occupancy probability of the sample trajectory. The first term of this bound matches the complexity in the case with independent samples drawn from the stationary distribution of the trajectory. The second term reflects the expense taken for the empirical distribution of the Markovian trajectory to reach a steady state, which is incurred at the very beginning and becomes amortized as the algorithm runs. Encouragingly, the above bound improves upon the state-of-the-art result by a factor of at least |S||A|. Further, the scaling on the discount complexity can be improved by means of variance reduction.

We investigate the sample efficiency of reinforcement learning in a $\gamma$-discounted infinite-horizon Markov decision process (MDP) with state space S and action space A, assuming access to a generative model. Despite a number of prior work tackling this problem, a complete picture of the trade-offs between sample complexity and statistical accuracy is yet to be determined. In particular, prior results suffer from a sample size barrier, in the sense that their claimed statistical guarantees hold only when the sample size exceeds at least $ |S| |A| / (1-\gamma)^2 $ (up to some log factor). The current paper overcomes this barrier by certifying the minimax optimality of model-based reinforcement learning as soon as the sample size exceeds the order of $ |S| |A| / (1-\gamma) $ (modulo some log factor). More specifically, a perturbed model-based planning algorithm provably finds an $\epsilon$-optimal policy with an order of $ |S| |A| / ((1-\gamma)^3\epsilon^2 ) $ samples (up to log factor) for any $0< \epsilon < 1/(1-\gamma)$. Along the way, we derive improved (instance-dependent) guarantees for model-based policy evaluation. To the best of our knowledge, this work provides the first minimax-optimal guarantee in a generative model that accommodates the entire range of sample sizes (beyond which finding a meaningful policy is information theoretically impossible).

In this work, we propose a novel non-orthogonal pilot design framework to tackle the pilot contamination problem in multi-cell massive multiple input multiple output (MIMO) systems. Assuming the minimum mean square error (MMSE) estimators are adopted at the base stations (BSs), we design pilot signals under power constraints by minimizing the total mean square errors (MSEs) of the MMSE estimators of all BSs. The pilot design problem is difficult to solve due to the non-convex objective function. A linearized alternating direction method of multipliers (L-ADMM) algorithm is introduced to solve the above non-convex optimization problem. The L-ADMM algorithm could approximate the objective function in a linear form, which makes the original problem solvable. In addition, a new non-orthogonal pilot design problem that maximizes the total spectral efficiency of all users in the cellular network is established. We show that the proposed L-ADMM-based pilot design method can be directly extended to solve it. Finally, numerical simulations validate that the proposed pilot design framework can achieve higher channel estimation accuracy and uplink achievable sum rate compared to the state-of-the-art approaches with less computational complexity.

The distributions of input data are very important for learning machines, such as the convex universal learning machines (CULMs). The CULMs are a family of universal learning machines with convex optimization. However, the computational complexity is a crucial problem in CULMs, because the dimension of the nonlinear mapping layer (the hidden layer) of the CULMs is usually rather large in complex system modeling. In this article, we propose an efficient quantization method called Probability density Rank-based Quantization (PRQ) to decrease the computational complexity of CULMs. The PRQ ranks the data according to the estimated probability densities and then selects a subset whose elements are equally spaced in the ranked data sequence. We apply the PRQ to kernel ridge regression (KRR) and random Fourier feature recursive least squares (RFF-RLS), which are two typical algorithms of CULMs. The proposed method not only keeps the similarity of data distribution between the code book and data set but also reduces the computational cost by using the kd-tree. Meanwhile, for a given data set, the method yields deterministic quantization results, and it can also exclude the outliers and avoid too many borders in the code book. This brings great convenience to practical applications of the CULMs. The proposed PRQ is evaluated on several real-world benchmark data sets. Experimental results show satisfactory performance of PRQ compared with some state-of-the-art methods.

Millimeter wave (mmWave) communication is a promising technology for future outdoor cellular systems. However, the abrupt channel change is more prone to occur over mmWave band compared to conventional frequencies, which will degrade the system performance. Hence, it is important to detect the channel change accurately for preparation of re-estimating the channel state information (CSI). In this paper, we attempt to solve the channel change problem from the perspective of change-point detection. By exploiting the low-rank characteristic of mmWave massive multiple-input multiple-output (MIMO) channel, the received signals can be viewed as data points in a subspace superimposed with noises. Then a cumulative sum (CUSUM)-based subspace change-point detection algorithm is designed to detect the mmWave channel change. The method can work without the aid of pilot signals and is of low computational complexity and memory requirement. Results are provided to validate the satisfactory of the proposed method.

Compressed sensing seeks to recover an unknown sparse vector from undersampled rate measurements. Since its introduction, there have been enormous works on compressed sensing that develop efficient algorithms for sparse signal recovery. The restricted isometry property (RIP) has become the dominant tool used for the analysis of exact reconstruction from seemingly undersampled measurements. Although the upper bound of the RIP constant has been studied extensively, as far as we know, the result is missing for the lower bound. In this work, we first present a tight lower bound for the RIP constant, filling the gap there. The lower bound is at the same order as the upper bound for the RIP constant. Moreover, we also show that our lower bound is close to the upper bound by numerical simulations. Our bound on the RIP constant provides an information-theoretic lower bound about the sampling rate for the first time, which is the essential question for practitioners.

Labelled data are often required to train an acoustic scene classification system. However, it is time-consuming and expensive to label the data manually. An unsupervised clustering algorithm can be used to facilitate the labelling process by dividing the acoustic data into different categories. Nevertheless, it can be problematic to run a clustering algorithm with growing data volume and dimension due to the sharp increase in the computational and memory costs. We propose a new streaming based subspace clustering algorithm which allows the data to be clustered on the fly, and also resolves data points in the overlapping regions of two subspaces by augmenting the learned low-rank representation with the original data samples. Experimental results show that our method can achieve the clustering objective for overwhelmingly high-volume data in an online fashion, while retaining good accuracy and reducing the memory cost significantly.

Hyperspectral images (HSIs) clustering problem is a challenge and valuable task due to its inherent complexity and abundant spectral information. Sparse subspace clustering (SSC) and SSC-based methods are widely used in this problem and demonstrate excellent performance. However, considering that HSIs are usually of high dimension, these methods have expensive computing complexity because of the usage of SSC. To solve this problem, we propose a novel approach called SuperPixel and Angle-based HyperSpectral Image Clustering (SPAHSIC). It first extracts the local spectral and spatial information between pixels by superpixel segmentation, and then applies spectral clustering on the similarity matrix built based on subspace principal angles. We implement experiments on real datasets and get a high accuracy, which indicates the effectiveness of our algorithm.

Multiple-input multiple-output (MIMO) millimeter wave (mmWave) communication is a key technology for next generation wireless networks. As the number of antennas becomes larger and the transmission bandwidth becomes wider, the array steering vectors would vary at different subcarriers, causing the beam squint effect. In this case, the conventional channel model is no longer applicable, especially for the mmWave massive MIMO system. In this paper, we first explain the influence of the beam squint effect from the array signal processing perspective and then investigate the angle-delay sparsity of mmWave transmission. We next design a compressive sensing (CS) algorithm based on shift-invariant block-sparsity that can jointly compute the off-grid angles, the off-grid delays, and the complex gains of the multi-path channel. Compared to either the conventional channel model, or the existing on-grid algorithms, the proposed one more accurately reflects the mmWave channel and is shown to yield better performance of uplink channel estimation.

Decentralized computing is widely used for multiagent systems since it works without a central computing node. In this paper, we develop a first-order algorithm for decentralized consensus optimization that is more energy efficient than the current state-of-the-art. Our algorithm is suitable for application scenarios such as networks of wireless sensors and Internet of Things, where some agents have limited (battery) energy. We call our algorithm walk proximal gradient (WPG), which passes a token through a walk (a succession of nodes) in the graph. The agents that are visited during the walk compute the gradients of their private functions and update the token. We analyze WPG where the walk is the repetition of a Hamiltonian cycle and show that the token converges to the consensual solution faster (in terms of energy consumption) than existing gradient-based decentralized methods. We also generalize the analysis to the non-Hamiltonian graphs. Numerical experiments are presented to validate the energy efficiency of our algorithm.

In a change-point detection problem, a sequence of signals switches from one distribution to another at an unknown time step, and the goal is to quickly and reliably detect this change. By providing new insight into signal processing and data analysis, graph signal processing promises various applications including image processing and sensor network analysis, and becomes an emerging field of research. In this work, we formulate the problem of change-point detection on graph. Under the reasonable assumption of normality, we propose a CUSUM-based algorithm for change-point detection with an arbitrary, unknown and perhaps time-varying mean shift after the change-point. We further propose a decentralized, distributed algorithm, which requires no fusion center, to reduce computational complexity, as well as costs and delays of communication. Numerical results on both synthetic and real-world data demonstrate that our algorithms are efficient and accurate.

Phase retrieval has been an attractive problem, and many algorithms have been proposed. Randomized Kaczmarz method is a fast iterative method with good performance in both convergence rate and computational cost with theoretical analysis. However, they all assume that the iteratively updated variables and the original data are independent, which is not true in reality. In this paper, we study for the first time the convergence analysis of this method in the real case, where only a finite number of measurements are available. Specifically, we theoretically prove the linear rate of convergence for the phase retrieval via randomized Kaczmarz algorithm without independence assumption.

Sampling and reconstruction is a fundamentally important problem in the field of graph signal processing. Many works have been contributed to reconstructing bandlimited signals from measurements taken on a known subset of vertices. However, in some cases, the vertex defects occur randomly over the graph. In such situation, the existing graph signal reconstruction methods fail to deal with such blind reconstruction problem. In this paper, we formulate the blind reconstruction problem as Mixed-Integer Nonlinear Programming, and propose a Joint Detection and Reconstruction (JDR) method to simultaneously detect the vertices' working states and reconstruct the bandlimited signal. The convergence property of the proposed method is analyzed. In the experimental part, both synthetic dataset and real-world dataset are applied to verify the proposed methods.

In this work we propose to fit a sparse logistic regression model by a weakly convex regularized nonconvex optimization problem. The idea is based on the finding that a weakly convex function as an approximation of the ℓ0pseudo norm is able to better induce sparsity than the commonly used ℓ1norm. For a class of weakly convex sparsity inducing functions, despite the nonconvexity, the algorithm proposed to solve the problem is based on proximal gradient descent, which allows the use of convergence acceleration techniques and stochastic gradient. Then the general framework is applied to a specific weakly convex function, and the solution method is instantiated as an iterative firm-shrinkage algorithm, of which the effectiveness is demonstrated in numerical experiments.

Multiple-Input-Multiple-Output (MIMO) communication systems have seen wide application due to its performance benefits such as multiplexing gain. For MIMO systems with non-ergodic Gaussian channel, a conjecture regarding its outage probability has been proposed by Telatar in [1] and long considered true. A special single-output case of this conjecture has been proved theoretically. In this work, we address the special Two-Input-Multiple-Output (TIMO) case, and show that the conjecture is untrue. A concrete counter-example is proposed and verified both theoretically and by numerical experiments. This result rejects the decades-long conjecture and provides interesting insight into the symmetry of MIMO systems.

Sparse subspace clustering (SSC) is a state-of-the-art method for clustering high-dimensional data points lying in a union of low-dimensional subspaces. However, while ℓ1optimization-based SSC algorithms suffer from high computational complexity, other variants of SSC, such as orthogonal-matching-pursuit-based SSC (OMP-SSC), lose clustering accuracy in pursuit of improving time efficiency. In this letter, we propose a novel active OMP-SSC, which improves clustering accuracy of OMP-SSC by adaptively updating data points and randomly dropping data points in the OMP process, while still enjoying the low computational complexity of greedy pursuit algorithms. We provide heuristic analysis of our approach and explain how these two active steps achieve a better tradeoff between connectivity and separation. Numerical results on both synthetic data and real-world data validate our analyses and show the advantages of the proposed active algorithm.

An OMP-like covariance-assisted matching pursuit (CAMP) method has recently been proposed. Given a prior knowledge of the covariance and mean of the sparse coefficients, CAMP balances the least squares estimator and the prior knowledge by leveraging the Gauss–Markov theorem. In this letter, we study the performance of CAMP in the framework of restricted isometry property (RIP). It is shown that under some conditions on RIP and the minimum magnitude of the nonzero elements of the sparse signal, CAMP with sparse level$K$can recover the exact support of the sparse signal from noisy measurements.$l_2$bounded noise and Gaussian noise are considered in our analysis. We also discuss the extreme conditions of noise (e.g., the noise power is infinite) to simply show the stability of CAMP.

Dimension reduction plays an essential role when decreasing the complexity of solving large-scale problems. The well-known Johnson-Lindenstrauss (JL) Lemma and Restricted Isometry Property (RIP) admit the use of random projection to reduce the dimension while keeping the Euclidean distance, which leads to the boom of sparsity related signal processing. Recently, successful applications of sparse models in computer vision and machine learning have increasingly hinted that the underlying structure of high dimensional data looks more like a union of subspaces (UoS). In this paper, motivated by JL Lemma, we study for the first time the distance-preserving property of Gaussian random projection matrices for two subspaces based on knowledge of Grassmann manifold. We theoretically prove that with high probability the affinity or the distance between two compressed subspaces are concentrated on their estimates. Numerical experiments verify the theoretical work.

This paper addresses image classification through learning a compact and discriminative dictionary efficiently. Given a structured dictionary with each atom (columns in the dictionary matrix) related to some label, we propose crosslabel suppression constraint to enlarge the difference among representations for different classes. Meanwhile, we introduce group regularization to enforce representations to preserve label properties of original samples, meaning the representations for the same class are encouraged to be similar. Upon the crosslabel suppression, we donot resort to frequently-used ℓ0-norm or ℓ1-norm for coding, and obtain computational efficiency without losing the discriminative power for categorization. Moreover, two simple classification schemes are also developed to take full advantage of the learnt dictionary. Extensive experiments on six data sets, including face recognition, object categorization, scene classification, texture recognition, and sport action categorization are conducted, and the results show that the proposed approach can outperform lots of recently presented dictionary algorithms on both recognition accuracy and computational efficiency.

Discovering the underlying structure of a high-dimensional signal or big data has always been a challenging topic, and has become harder to tackle especially when the observations are exposed to arbitrary sparse perturbations. In this paper, built on the model of a union of subspaces (UoS) with sparse outliers and inspired by a basis pursuit strategy, we exploit the fundamental structure of a Grassmann manifold, and propose a new technique of pursuing the subspaces systematically by solving a non-convex optimization problem using the alternating direction method of multipliers. This problem as noted is further complicated by non-convex constraints on the Grassmann manifold, as well as the bilinearity in the penalty caused by the subspace bases and coefficients. Nevertheless, numerical experiments verify that the proposed algorithm, which provides elegant solutions to the sub-problems in each step, is able to de-couple the subspaces and pursue each of them under time-efficient parallel computation.

Square-root least absolute shrinkage and selection operator (Lasso), a variant of Lasso, has recently been proposed with a key advantage that the optimal regularization parameter is independent of the noise level in the measurements. In this letter, we introduce a class of nonconvex sparsity-inducing penalties to the square-root Lasso to achieve better sparse recovery performance over the convex counterpart. The resultant formulation is converted to a nonconvex but multiconvex optimization problem, i.e., it is convex in each block of variables. Alternating direction method of multipliers is applied as the solver, according to which two efficient algorithms are devised for row-orthonormal sensing matrix and general sensing matrix, respectively. Numerical experiments are conducted to evaluate the performance of the proposed methods.

In solving the problem of sparse recovery, non-convex techniques have been paid much more attention than ever before, among which the most widely used one is ℓpminimization with p ∈ (0, 1). It has been shown that the global optimality of ℓpminimization is guaranteed under weaker conditions than convex ℓ1minimization, but little interest is shown in the local optimality, which is also significant since practical non-convex approaches can only get local optimums. In this work, we derive a tight condition in guaranteeing the local optimality of ℓpminimization. For practical purposes, we study the performance of an approximated version of ℓpminimization, and show that its global optimality is equivalent to that of ℓpminimization when the penalty approaches the ℓp“norm”. Simulations are implemented to show the recovery performance of the approximated optimization in sparse recovery.

Stochastic optimization finds wide application in signal processing, online learning, and network problems, especially problems processing large-scale data. We propose an Incremental Constraint Averaging Projection Method (ICAPM) that is tailored to optimization problems involving a large number of constraints. The ICAPM makes fast updates by taking sample gradients and averaging over random constraint projections. We provide a theoretical convergence and rate of convergence analysis for ICAPM. Our results suggests that averaging random projections significantly improves the stability of the solutions. For numerical tests, we apply the ICAPM to an online classification problem and a network consensus problem.

Sparse subspace clustering (SSC) is a technique to partition unlabeled samples according to the subspaces they locate in. With the rapid increase of data amount, efficiently downsampling a big dataset, while at the same time keeping the structure of subspaces, becomes an important topic for SSC. In order to reduce the computational cost while preserving clustering accuracy, a new approach of SSC with downsampling (SSCD) is proposed in this paper. In SSCD, the numbers of samples located in respective subspaces are estimated utilizing the ℓ1norm of the sparse representation. Then a downsampling strategy is designed to decimate samples with the probabilities that are in reverse ratio to the amounts of samples in respective subspaces. As a consequence, the samples in different subspaces are expected to be balanced after the downsampling operation. Theoretical analysis proves the correctness of the proposed strategy. Numerical simulations also verify the efficiency of SSCD.

In this paper, we work on the problem of subspace estimation from random downsamplings of its projection matrix. An optimization problem on the Grassmann manifold is formulated for projection matrix completion, and an iterative gradient descend line-search algorithm on the Grassmann manifold (GGDLS) is proposed to solve such optimization problem. The convergence of the proposed algorithm has theoretical guarantee, and numerical experiments verify that the required sampling number for successful recovery of a rank s projection matrix in ℝN×Nwith probability 1 is 2s(N - s) in the noiseless cases. Compared with some reference algorithms, in the noiseless scenario, the proposed algorithm is very time efficient, and the required sampling number is rather small for successful recovery. In the noisy scenario, the proposed GGDLS is remarkably robust against the noise both under high measurement SNR and low measurement SNR.

Sparse signal recovery in the static case has been well studied under the framework of Compressive Sensing (CS), while in recent years more attention has also been paid to the dynamic case. In this paper, enlightened by the idea of modified-CS with partially known support, and based on a non-convex optimization approach, we propose the dynamic zero-point attracting projection (DZAP) algorithm to efficiently recover the slowly time-varying sparse signals. Benefiting from the temporal correlation within signal structures, plus an effective prediction method of the future signal based on previous recoveries incorporated, DZAP achieves high-precision recovery with less measurements or larger sparsity level, which is demonstrated by simulations on both synthetic and real data, accompanied by the comparison with other state-of-the-art reference algorithms.

The literature on sparse recovery often adopts the lp “norm” ( p ∈ [0,1]) as the penalty to induce sparsity of the signal satisfying an underdetermined linear system. The performance of the corresponding lp minimization problem can be characterized by its null space constant. In spite of the NP-hardness of computing the constant, its properties can still help in illustrating the performance of lp minimization. In this letter, we show the strict increase of the null space constant in the sparsity level k and its continuity in the exponent p. We also indicate that the constant is strictly increasing in p with probability 1 when the sensing matrix A is randomly generated. Finally, we show how these properties can help in demonstrating the performance of lp minimization, mainly in the relationship between the the exponent p and the sparsity level k.

Structures play a significant role in the field of signal processing. As a representative of structural data, low rank matrix along with its restricted isometry property (RIP) has been an important research topic in compressive signal processing. Subspace projection matrix is a kind of low rank matrix with additional structure, which allows for further reduction of its intrinsic dimension. This leaves room for improving its own RIP, which could work as the foundation of compressed subspace projection matrix recovery. In this work, we study the RIP of subspace projection matrix under random orthonormal compression. Considering the fact that subspace projection matrices of s dimensional subspaces in RNform an s(N - s) dimensional submanifold in RN×N, our main concern is transformed to the stable embedding of such submanifold into RN×N. The result is that by O(s(N - s)log N) number of random measurements the RIP of subspace projection matrix is guaranteed.

A recent trend in compressed sensing is to consider nonconvex optimization techniques for sparse recovery. The important case of F-minimization has become of particular interest, for which the exact reconstruction condition (ERC) in the noiseless setting can be precisely characterized by the null space property (NSP). However, little work has been done concerning its robust reconstruction condition (RRC) in the noisy setting. We look at the null space of the measurement matrix as a point on the Grassmann manifold, and then study the relation between the ERC and RRC sets, denoted as ΩJand ΩJr, respectively. It is shown that ΩJis the interior of ΩJ, from which a previous result of the equivalence of ERC and RRC for ℓp-minimization follows easily as a special case. Moreover, when F is nondecreasing, it is shown that Ω̅J\int(ΩJ) is a set of measure zero and of the first category. As a consequence, the probabilities of ERC and RRC are the same if the measurement matrix A is randomly generated according to a continuous distribution. Quantitatively, if the null space N(A) lies in the d-interior of ΩJ, then RRC will be satisfied with the robustness constant C=2+2d/dσmin(AT); and conversely, if RRC holds with C=2-2d/dσmax(AT), then N(A) must lie in d-interior of ΩJ. We also present several rules for comparing the performances of different cost functions. Finally, these results are capitalized to derive achievable tradeoffs between the measurement rate and robustness with the aid of Gordon's escape through the mesh theorem or a connection between NSP and the restricted eigenvalue condition.

Existing literatures suggest that sparsity is more likely to be induced with non-convex penalties, but the corresponding algorithms usually suffer from multiple local minima. In this paper, we introduce a class of sparsity-inducing penalties and provide the convergence guarantees of a non-convex approach for sparse recovery using regularized least squares. Theoretical analysis demonstrates that under some certain conditions, if the non-convexity of the penalty is below a threshold (which is in inverse proportion to the distance between the initialization and the sparse signal), the sparse signal can be stably recovered. Numerical simulations are implemented to verify the theoretical results in this paper and to compare the performance of this approach with other references.

In the proposed model of adaptive filtering network, distributed learning algorithm works cooperatively to identify separated unknown systems, which have different impulse responses. Specifically, JS-CoLMS algorithm is proposed to iteratively learn the unknown systems and the joint sparsity, based on a stochastic gradient approach and a subdifferentiable sparse-inducing penalty approximating the l2,0norm. The superior performance of the proposed algorithm and its relation to l0-LMS and Leaky LMS are briefly discussed and verified by numerical experiments.

Signal processing on graphs is an emerging field that attracts increasing attention. For applications such as multiscale transforms on graphs, it is often necessary to get a coarsened version of graph signal with its underlying graph. However, most of the existing methods use only topology information but no property of graph signals to complete the process. In this paper, we propose a novel graph signal coarsening method with spectral invariance, which means both the spectrum of the graph and the spectrum of the graph signal are approximately kept invariant. The problem is formulated into an optimization problem and is solved by projected subgradient method. Experiment results verify the effectiveness of the coarsening method.

In this paper, the robust off-grid recovery of the compressed signals with atomic norm-regularized least-squares problem is studied. The aim of the recovery is to reconstruct the original signal and to detect its off-grid support set. The general optimality conditions for the solution to this problem and its dual problem are proposed and discussed. A method based on dual certification to detect the support set is introduced and proved to be effective. As a specific case, the target signal is further assumed to have unknown line spectrum. Then the problem is also an estimation of a low dimensional subspace which is indexed by continuous parameters, yet the dimension itself is unknown. Under these presumptions, the squared-error of the reconstruction is derived. Finally, numerical experiments are demonstrated in such case to validate the effectiveness of the method and the plausibility of the theory.

Based on affine projection algorithm (APA) in adaptive filtering and the technique of parallel computing, we propose a novel algorithm called ℓ0-APA with its parallel implementation for sparse system identification and sparse signal recovery. For sparse system identification, parallel ℓ0-APA can serve as an effective approach for practical hardware implementation, since it lowers the requirement on the processors' clock speed. For sparse signal recovery, it can significantly reduce the convergence time. Prior algorithms such as ℓ0-LMS and ℓ0-ZAP can be seen as special cases of ℓ0-APA. Finally the performance of the proposed algorithm is analyzed and verified by numerical experiments.

Compressive sensing (CS) is a data acquisition technique that measures sparse or compressible signals at a sampling rate lower than their Nyquist rate. Results show that sparse signals can be reconstructed using greedy algorithms, often requiring prior knowledge such as the signal sparsity or the noise level. As a substitute to prior knowledge, cross validation (CV), a statistical method that examines whether a model overfits its data, has been proposed to determine the stopping condition of greedy algorithms. This paper analyses cross validation in a general compressive sensing framework. Furthermore, we provide both theoretical analysis and numerical simulations for a cross-validation modification of orthogonal matching pursuit, referred to as OMP-CV, which has good performance in sparse recovery.

This paper aims to provide theoretical guarantees via non-convex optimization for sparse recovery. It is shown that the sparse signal is the unique local optimal solution within a neighborhood, which contains the least squares solution if the sparsity-inducing penalties are not too non-convex. The idea of projected subgradient method is generalized to solve this non-convex optimization problem. A uniform approximate projection is applied in the projection step to make the algorithm more computationally tractable. The theoretical convergence analysis of the proposed method, approximate projected generalized gradient (APGG), is performed in the noisy scenario. The result reveals that if the non-convexity of the penalties is under a threshold, the bound of the recovery error is linear in both the noise bound and the step size. Numerical simulations are performed to test the performance of APGG and verify its theoretical analysis.

The idea of backtracking has been incorporated into the matching pursuit algorithms in sparse recovery, for example, subspace pursuit (SP) and compressive sampling matching pursuit (CoSaMP), to improve the recovery performance. In each iteration, a supplement set of size K or 2K is added to the candidate set to re-evaluate their reliability and then discard the unreliable indices, where K is the sparsity level of the original sparse signal. Yet the optimal choice of the size of the supplement set is still unclear. This paper aims to provide comprehensive analysis on the optimal choice of the size. The optimality is twofold: performance guarantees and computational complexity. By two theorems,we provide theoretical guarantees for the supplement set of arbitrary size, and computational complexity needed for perfect recovery. Numerical simulations demonstrate that a moderate size, such as 0.25K, results in computational efficiency without loss of recovery quality.

This paper focuses on the problem of Linear Prediction (LP) constrained by sparse residuals. After reformulating the problem to finding the largest linear correlated strict subset in a given vector set, a greedy method is proposed to determine the support of the sparse residuals iteratively by testing each entry with respective temporary prediction error. The greedy method is then simplified to reduce computational cost. Compared with reference algorithms and conventional LP model, the proposed methods are tested in the speech coding scenario. Experiment results demonstrate that the proposed greedy methods work well and suggest that LP with sparse residuals provides accurate estimation, and is much practical in the scenarios that more bits are allocated for coding residuals.

In recent years, sparse representation is adopted to improve the quality of noise corrupted speech. However, the representation of noise is also found to be sparse in some special cases, which degrades the performance of sparsity based speech enhancement. An adaptive speech enhancement algorithm using sparse prior information is proposed in this paper. In the proposed method, speech enhancement is casted to an optimization problem, where linear prediction (LP) residual and DCT coefficients are combined and adopted as the representation of speech to ensure that noise is dense in the such domain. Other features, including speech energy, noise energy, and interframe correlation are also considered as constraints to improve the quality and intelligibility of recovered speech. Experiment results show that the proposed algorithm exceeds the reference algorithms in various noise scenarios, especially, in the cases of narrowband noise and low SNR.

Recent work in compressed sensing has shown the possibility reducing the number of measurements via non-convex optimization methods. Most of these methods can be studied in the general framework called “F-minimization”, for which the relation between the noiseless exact recovery condition (ERC) and noisy robust recovery condition (RRC) was not fully understood. In this paper, we associate each set of nulls spaces of the measurement matrices satisfying ERC/RRC as a subset of a Grassmannian, and show that the RRC set is exactly the interior of the ERC set. Then, a previous result of the equivalence of ERC and RRC for lp-minimization follows easily as a special case. We also show under some mild but necessary additional assumption that the ERC and RRC sets differ by a set of measure zero.

Device‐to‐device (D2D) communication underlaying cellular systems is proposed to support short‐range data‐intensive services. In a D2D‐enabled system, a closely located user pair is allowed to communicate over a direct data link, instead of being relayed through the network. In this study, based on the power control framework in traditional cellular networks, a combined power control and link selection algorithm with temporary removal for D2D‐enabled systems is proposed. It is proved that the proposed algorithm converges to the optimal power and link selection vector in all feasible systems. In an infeasible system, convergence of the temporary removal algorithm cannot be guaranteed. Therefore two adaptive gradual removal algorithms are proposed, which are suitable for lightly and heavily loaded systems, respectively. Numerical results show that both of the proposed algorithms outperform the existing ones in terms of outage probability and convergence rate.

The newly proposed l 1 norm constraint zero‐point attraction least mean square algorithm (ZA‐LMS) demonstrates excellent performance on exact sparse system identification. However, ZA‐LMS has less advantage against standard LMS when the system is near sparse. Thus, in this study, firstly the near sparse system (NSS) modelling by generalised Gaussian distribution is recommended, where the sparsity is defined accordingly. Second, two modifications to the ZA‐LMS algorithm have been made. The l 1 norm penalty is replaced by a partial l 1 norm in the cost function, enhancing robustness without increasing the computational complexity. Moreover, the ZA item is weighted by the magnitude of estimation error which adjusts the ZA force dynamically. By combining the two improvements, Dynamic Windowing ZA‐LMS (DWZA‐LMS) algorithm is further proposed, which shows better performance on NSS identification. In addition, the mean‐square performance of DWZA‐LMS algorithm is analysed. Finally, computer simulations demonstrate the effectiveness of the proposed algorithm and verify the result of theoretical analysis.

In this paper, we consider orthogonal matching pursuit (OMP) algorithm for multiple measurement vectors (MMV) problem. The robustness of OMPMMV is studied under general perturbations-when the measurement vectors as well as the sensing matrix are incorporated with additive noise. The main result shows that although exact recovery of the sparse solutions is unrealistic in noisy scenario, recovery of the support set of the solutions is guaranteed under suitable conditions. Specifically, a sufficient condition is derived that guarantees exact recovery of the sparse solutions in noiseless scenario.

In this paper, we consider compressed sensing (CS) of block-sparse signals, i.e., sparse signals that have nonzero coefficients occurring in clusters. An efficient algorithm, called zero-point attracting projection (ZAP) algorithm, is extended to the scenario of block CS. The block version of ZAP algorithm employs an approximate l2,0norm as the cost function, and finds its minimum in the solution space via iterations. For block sparse signals, an analysis of the stability of the local minimums of this cost function under the perturbation of noise reveals an advantage of the proposed algorithm over its original non-block version in terms of reconstruction error. Finally, numerical experiments show that the proposed algorithm outperforms other state of the art methods for the block sparse problem in various respects, especially the stability under noise.

The Modulated Wideband Converter (MWC) is a recently proposed analog-to-digital converter (ADC) based on Compressive Sensing (CS) theory. Unlike conventional ADCs, its quantization reference voltage, which is important to the system performance, does not equal the maximum amplitude of original analog signal. In this paper, the quantization reference voltage of the MWC is theoretically analyzed and the conclusion demonstrates that the reference voltage is proportional to the square root of q, which is a trade-off parameter between sampling rate and number of channels. Further discussions and simulation results show that the reference voltage is proportional to the square root of Nq when the signal consists of N narrowband signals.

Most of the approaches in the application of network coding either require the overhearing opportunity or have bad interaction with TCP. A new mechanism, named TCP-I2NC, is proposed in this paper to incorporate network coding into TCP in interference-free multi-radio multi-channel wireless mesh networks where there are nearly no overhearing opportunities. Multiple TCP flows are coded together and forwarded in block by hop-by-hop ACK and retransmissions in TCP-I2NC. Several encoding blocks are working simultaneously to effectively utilize available bandwidth. However the maximum of encoding blocks is adaptively adjusted according to the bandwidth, propagation delay and packet loss rate of a wireless link, and also back pressure algorithm is used to perform flow and scheduling control. The end-to-end delay is optimized so that TCP-I2NC is applicable to delay-sensitive applications. Simulations show that our mechanism both significantly improves the throughput of TCP and derives a relatively short end-to-end delay as losses increase. And the delay jitter of TCP-I2NC is also very small. TCP-I2NC also achieves complete fairness in resource allocation.

In this paper, a routing algorithm for Wireless Mesh Networks (WMNs) over Ultra Wide Band (UWB) is proposed for High Definition (HD) video transmission. In order to support multiple services smoothly over UWB, a new routing algorithm called Service Aided UWB Routing is developed. Unlike conventional routing algorithms, the proposed method is driven by application services' requirements, which determines the relays and the corresponding resources allocation for various types of application packets, thus reducing possible interferences between different streams. The proposed routing approach significantly outperforms the traditional routing algorithms, since it is capable of adjusting routing policies dynamically according to application services in fast changing topologies, which makes it especially suitable for the Video on Demand (VoD) application over UWB.

We propose a new approach to adaptive system identification when the system model is sparse. The approach applies ℓ1relaxation, common in compressive sensing, to improve the performance of LMS-type adaptive methods. This results in two new algorithms, the zero-attracting LMS (ZA-LMS) and the reweighted zero-attracting LMS (RZA-LMS). The ZA-LMS is derived via combining a ℓ1norm penalty on the coefficients into the quadratic LMS cost function, which generates a zero attractor in the LMS iteration. The zero attractor promotes sparsity in taps during the filtering process, and therefore accelerates convergence when identifying sparse systems. We prove that the ZA-LMS can achieve lower mean square error than the standard LMS. To further improve the filtering performance, the RZA-LMS is developed using a reweighted zero attractor. The performance of the RZA-LMS is superior to that of the ZA-LMS numerically. Experiments demonstrate the advantages of the proposed filters in both convergence rate and steady-state behavior under sparsity assumptions on the true coefficient vector. The RZA-LMS is also shown to be robust when the number of non-zero taps increases.

In order to improve the performance of least mean square (LMS) based system identification of sparse systems, a new adaptive algorithm is proposed which utilizes the sparsity property of such systems. A general approximating approach onl0norm-a typical metric of system sparsity, is proposed and integrated into the cost function of the LMS algorithm. This integration is equivalent to add a zero attractor in the iterations, by which the convergence rate of small coefficients, that dominate the sparse system, can be effectively improved. Moreover, using partial updating method, the computational complexity is reduced. The simulations demonstrate that the proposed algorithm can effectively improve the performance of LMS-based identification algorithms on sparse system.

In this paper, a novel color-based target representation scheme is proposed for object tracking. Different from those commonly used models, where color-based features are extracted from the object region only, the proposed solution takes the background information into account as well. A transition region is defined which contains the background area around the target object. Thus the target object is represented by the color distribution estimated from both the object region and the transition region. Negative weights are assigned to the pixels in the transition region so that only the distinct features which are distinguishable from the background are extracted to represent the target object. Experimental results suggest that the proposed model outperforms the traditional model in the scenarios where surrounding background is similar to the target object or each part of the object has similar appearance

Within the framework that two filters are working in parallel, Stochastic Taps NLMS (ST-NLMS) effectively chooses only active taps for adaptation, resulting in a good transient behavior when identifying long, sparse, echo path like systems. However, ST-NLMS still suffers from the inherent limitation of LMS. This necessitates a compromise between the opposing fundamental requirements of fast convergence rate and small misadjustment. Following the same block diagram as ST-NLMS, the Stochastic Step-size NLMS (SS-NLMS) scheme is proposed and integrated into the ST-NLMS framework. The combination leads to a novel algorithm called STS-NLMS, which adjusts step-size and active taps simultaneously. Extensive experiments demonstrate that substantial improvements in the speed of convergence are achieved by using the proposed algorithm in stationary environment outperforming both NLMS and ST-NLMS with the same small level of misadjustment. In addition, the proposed algorithm shows superior tracking capability when the system is subjected to an abrupt disturbance. Furthermore, if nonstationary environment is considered, the performance of the proposed algorithm is still satisfying.

A novel method is presented to detect roads in synthetic aperture radar (SAR) images. A multi-segmented poly-line model is introduced to provide a more accurate description of the road as well as to ensure the road curve's smoothness in the model level. We then solve the road detection problem using the Bayesian tracking theory, where the particle filtering algorithm is adopted to provide a simple and consistent framework. The effectiveness and robustness of the proposed method is demonstrated by experimental results.

In many real applications for face recognition, such as surveillance photo identification, each subject only has one image sample for training which makes many supervised learning techniques fail to apply. Furthermore, since subject appearance has large variabilities due to aging, illumination and camera viewpoints, the face images to be identified are usually different from the stored templates. In this paper, a novel solution to this problem is proposed based on the well known unsupervised methodology, eigenface. We proposed a criterion to select the eigenfaces forming a feature subspace in which the intrapersonal variation is small compared to interpersonal variation and as well as most discriminating power is retained. The selection criterion maximizes the ratio between inter and intra personal variation, and at the same time takes total inter variation into account. Extensive experimentation following the FERET evaluation protocol indicates that the proposed scheme improves significantly the recognition performance.

Besides the traditional accesses to accelerate the convergence of the LMS algorithm, such as step-size control and input signal decorrelation, tap-length control is an emerging technique and attracts more and more attention. Many tap-length control schemes are proposed and most of them are based on the gradient search method. The sufficient condition for tap-length gradient adaption is obtained based on the assumption of white Gaussian input. The analysis reveals that two requirements should be satisfied when using the gradient method to search for optimum tap-length. One is that the unknown impulse response has a decay envelope, while the other requires that the number of the tap difference should be selected carefully.

This letter presents a novel variable-length least mean square algorithm, whose filter length is adjusted dynamically along the negative gradient direction of the squared estimation error. Compared with other variable-length algorithms, the proposed algorithm has faster convergence and more robust performance in diverse environments.

This letter analyzes the mean-square convergence of a deficient-length least mean-square adaptive filter whose length is less than that of the unknown system and proves that filter length and the envelope of impulse response are the important factors in convergence rate control. For the impulse response with an exponential decay envelope, which covers a large set of physical systems, e.g., acoustic echo path, an optimal filter length sequence is figured out to achieve the fastest convergence. The simulations of an exact exponential decay envelope and of a real-life echo path in a car environment are performed via computer, and the results validate our analysis well.