Semi-supervised learning (SSL) on graphs is critical in applications where labeled data are scarce and costly, yet existing graph-based methods often degrade under extreme label sparsity or class imbalance, yielding trivial or unstable solutions. We introduce \textbf{CombCut}, the first exact combinatorial optimization framework for multi-class graph-based semi-supervised learning that operates directly on binary one-hot assignments, without any convex relaxation or heuristic volume constraints. By employing a minorization–maximization (MM) scheme, CombCut transforms each step into a structured linear assignment problem solved efficiently via network-flow algorithms. Total unimodularity guarantees integral iterates, and our theoretical analysis establishes both monotonic ascent of the true discrete objective and convergence of every limit point to a Karush–Kuhn–Tucker (KKT) stationary solution of the original combinatorial problem. Our approach requires no hyperparameter tuning and scales near-linearly in the number of vertices. Empirical evaluation on MNIST, Fashion-MNIST, and CIFAR-10 with as few as 1–5 labels per class shows that CombCut excels in worst-case labeling scenarios, significantly outperforming state-of-the-art graph-SSL baselines and yielding more stable and accurate label propagation under severe supervision constraints.

We present a transformer-based model for credibility assessment, CREDiBERT (CREDibility assessment using Bi-directional Encoder Representations from Transformers), fine-tuned for Reddit submissions focusing on political discourse. We adopt a semi-supervised training approach for CREDiBERT, leveraging the community structure of Reddit. By encoding submission content using CREDiBERT and integrating it with a classification neural network, we improve the credibility assessment for Reddit submission by 3% in F1 score compared to existing methods. Additionally, we introduce a new version of the post-to-post network in Reddit that efficiently encodes user interactions to enhance the credibility assessment task by 8% in the F1 score. We demonstrate CREDiBERT's applicability by evaluating the susceptibility of Reddit communities to different topics and assessing the credibility score of unseen sources.

Social news websites, such as Reddit, have evolved into prominent platforms for sharing and discussing news. A key issue on social news websites is the formation of low-credibility communities, which often lead to the spread of highly biased or uncredible news. We develop a method to identify communities prone to uncredible or highly biased news within a social news website. We employ a user embedding pipeline that detects user communities based on their stances toward posts and news sources. We then project each community onto a credibility-bias space and analyze the distributional characteristics of each projected community to identify those that have a high risk of adopting beliefs with low credibility or high bias. This approach also enables the prediction of individual users' susceptibility to low-credibility content based on their community affiliation. Our results show that latent space clusters effectively indicate the credibility and bias levels of their users, with significant variance observed across clusters---a 34% difference in the users' susceptibility to low-credibility content and a 8.3% difference in the users' susceptibility to high political bias.

Abstract. Image forensics and counter forensics (CF) are two competing fields that have experienced significant developments in recent years. Interestingly, the use of histogram is popular in both forensic detectors and counter-forensic methods. In this work, we focus on the histogram-based CF methods; in particular, we propose a quasi-convex version of SSIM and MSSIM as the cost function of CF which helps in restricting search domain for optimal solution to the CF problem. Also, we propose two sub-optimal methods for this problem: (1) a gradient descent version of the optimal counter-forensics method (OCM) with the cost function MSSIM instead of MSE (which we call GDOCM), and (2) another method that employs unitary matrices as the transfer matrix (which we call UMM). We numerically compare the proposed methods with the OCM method in different settings including the common JPEG compression detection scenario. Our experiments confirm superiority of the proposed methods compared to OCM.

Graph representations of data offer a rich framework for advanced signal processing applications. However, in many practical scenarios, constructing the graph is computationally demanding, and storing it can be prohibitively expensive-often requiring significantly more memory than the signal itself. This paper introducesGraphLite, a novel algorithm tailored for one of the good performing graph learning methods, to compactly represent the learned graph through an auxiliary vector of the same dimension as the signal. This auxiliary representation, which consists of the inverse node degree profile, arises naturally from the structure of the optimal solution and can be pre-computed and stored alongside the signal. The result is a lightweight, lossless graph representation that retains compatibility with core graph signal processing (GSP) operations. GraphLite offers a flexible and memory-efficient tool for downstream tasks in applications where both online graph construction and storage are bottlenecks.

The Rényi Information Dimension (RID) is a fundamental measure for quantifying the compressibility of random variables with singularities in their distributions, extending beyond classical notions of sparsity. At a high level, RID represents the average number of bits required to encode i.i.d. samples of a random variable with high precision. For stochastic processes, two main extensions of RID exist: the information dimension rate (IDR) and the block information dimension (BID). A more recent approach to characterizing the compressibility of stochastic processes is through ϵ-achievable compression rates, which treat a random process as the limit of finite-dimensional random vectors and leverage tools from compressed sensing. However, the interplay between BID, IDR, and ϵ-achievable compression rates remains poorly understood. Furthermore, explicit values of IDR and BID are known only for a limited class of processes, such as i.i.d. sequences (i.e., discrete-time white noise) and moving-average (MA) processes. This paper investigates the IDR and BID of discrete-time Auto-Regressive Moving-Average (ARMA) processes and their relationship with ϵ-achievable compression rates when the excitation noise follows a discrete-continuous distribution. Specifically, we show that the RID and ϵ-achievable compression rates of such ARMA processes are equal to those of their excitation noise. In other words, despite the fact that ARMA process samples are not sparse, their compressibility matches that of their sparse excitation noise. To establish this result, we demonstrate that the singular components of the sample distribution are supported on affine sets, with relative dimensions that concentrate around the BID. Leveraging a known result on typical affinely singular sources, we further prove that in this setting, the RID coincides with ϵ-achievable compression rates. The findings of this paper provide new insights into the compressibility of locally correlated data with finite- or infinite-memory, which are commonly modeled using ARMA processes.

Learning a graph from data is the key to taking advantage of graph signal processing tools. Most of the conventional algorithms for graph learning require complete data statistics, which might not be available in some scenarios. In this work, we aim to learn a graph from incomplete time-series observations. From another viewpoint, we consider the problem of semi-blind recovery of time-varying graph signals where the underlying graph model is unknown. We propose an algorithm based on the method of block successive upperbound minimization (BSUM), for simultaneous inference of the signal and the graph from incomplete data. Simulation results on synthetic and real time-series demonstrate the performance of the proposed method for graph learning and signal recovery.

We address the problem of sparse selection of visual features for localizing a team of robots navigating in an unknown environment, where robots can exchange relative position measurements with neighbors. We select a set of the most informative features by anticipating their importance in robots localization by simulating trajectories of robots over a prediction horizon. Through theoretical proofs, we establish a crucial connection between graph Laplacian and the importance of features. We leverage a scalable randomized algorithm for sparse sums of positive semidefinite matrices to efficiently select a set of the most informative features.

A key element in the performance of a compressed sensing (CS) setup is the so called sensing matrix. It is known that the success of CS-based methods strongly rely on the properties of the employed sensing matrix. Random matrices are the widely-adopted choice due to their order-optimal performance and flexibility in size. In real world applications , however, random structures are rarely feasible. For this reason, the deterministic design of sensing matrices has been an ongoing research topic. In this paper, we introduce new classes of deterministic complex-valued sensing matrices based on algebraic curves. In particular, we design a number of algebraic-geometric codes with large minimum distances specifically for the construction of sensing matrices. Our approach is to find maximal curves in the Galois field F p m ‾ , and transform them into F p codes by a trace map. Invoking the Riemann-Roch theorem, we demonstrate that the resulting code has a large minimum distance compared to its length, which leads to a sensing matrix with small coherence value. For general m × n matrices, the Welch bound ( ≈ 1 m ) sets a universal lower-bound on the coherence value, and the bound is achievable only when n ≤ m 2 . In our designs, we are able to construct m × n matrices with n ranging from around 8 m to values larger than O ( m 2 ) by tuning the parameters. Meanwhile, the coherence of the designed matrices differ from the Welch bound by only an O ( log m ) factor. Simulation results indicate that the performance of our matrices in recovering sparse vectors from compressed measurements is superior or equivalent to Gaussian random matrices.

In this paper, we study the problem of estimating the direction of arrival (DOA) using a sparsely sampled uniform linear array (ULA). Based on an initial incomplete ULA measurements, our strategy is to choose a sparse subset of array elements for measuring the next snapshot. Then, we use a Hankel-structured matrix completion to interpolate for the missing ULA measurements. Finally, the source DOAs are estimated using a subspace method such as Prony on the fully recovered ULA. We theoretically provide a sufficient bound for the number of required samples (array elements) for perfect recovery. The numerical comparisons of the proposed method with existing techniques such as atomic-norm minimization and off-the-grid approaches confirm the superiority of the proposed method.

Abstract With the emergence of social networks and improvements in the internet speed, the video data has become an ever‐increasing portion of the global internet traffic. Besides the content, the quality of a video sequence is an important issue at the user end which is often affected by various factors such as compression. Therefore, monitoring the quality is crucial for the video content and service providers. A simple monitoring approach is to compare the raw video content (uncompressed) with the received data at the receiver. In most practical scenarios, however, the reference video sequence is not available. Consequently, it is desirable to have a general reference‐less method for assessing the perceived quality of any given video sequence. In this paper, a no‐reference video quality assessment technique based on video features is proposed. In particular, a long list of video features (21 sets of features, each consisting of 1 to 216 features) is considered and all possible combinations () for training an Extra Trees regressor is examined. This choice of the regressor is wisely selected and is observed to perform better than other common regressors. The results reveal that the top 20 performing feature subsets all outperform the existing feature‐based assessment methods in terms of the Pearson linear correlation coefficient (PLCC) or the Spearman rank order correlation coefficient (SROCC). Specially, the best performing regressor achieves on the test data over the KonVid‐1k dataset. It is believed that the results of the comprehensive comparison could be potentially useful for other feature‐based video‐related problems. The source codes of the implementations are publicly available.

The notion of compressibility of a random measure is a rather general concept which find applications in many contexts from data compression, to signal quantization, and parameter estimation. While compressibility for discrete and continuous measures is generally well understood, the case of discrete-continuous measures is quite subtle. In this paper, we focus on a class of multi-dimensional random measures that have singularities on affine lower-dimensional subsets. We refer to this class of random variables asaffinely singular. Affinely singular random vectors naturally arises when considering linear transformation of component-wise independent discrete-continuous random variables. To measure the compressibility of such distributions, we introduce the new notion of dimensional-rate bias (DRB) which is closely related to the entropy and differential entropy in discrete and continuous cases, respectively. Similar to entropy and differential entropy, DRB is useful in evaluating the mutual information between distributions of the aforementioned type. Besides the DRB, we also evaluate the the RID of these distributions. We further provide an upper-bound for the RID of multi-dimensional random measures that are obtained by Lipschitz functions of component-wise independent discrete-continuous random variables (X). The upper-bound is shown to be achievable when the Lipschitz function is$A \mathrm {X}$, where$A$satisfies${\mathrm{ SPARK}}({A_{m\times n}}) = m+1$(e.g., Vandermonde matrices). When considering discrete-domain moving-average processes with non-Gaussian excitation noise, the above results allow us to evaluate the block-average RID and DRB, as well as to determine a relationship between these parameters and other existing compressibility measures.

In this paper, we study the problem of ellipse recovery from blurred shape images. A shape image is a continuous-domain black and white (binary-valued) image in which the points of the same color form a shape. We assume to have a digitized version of the shape image which is a sampled and blurred version of the image using a 2D kernel (the point spread function); the resulting pixels may also be corrupted by additive noise. Our goal in this work is to recover the original continuous-domain image based on the available pixels when the shape image is an ellipse. Our approach is to represent an ellipse as the zero-level-set of a bivariate polynomial of degree 2 and estimate the involved 6 polynomial coefficients based on a deep neural network. Our model is trained end to end on a wide range of blurring setups with varying noise levels. Besides, the network is trained to recover the ellipse even when the available noisy pixels cover only a part of the ellipse. Simulation results validate the performance of the proposed method and indicate its superiority compared to the state of art methods.

The LoRa technology is considered as one of the most potential solutions for Internet of Things (IoT) in the near future. The existing LoRa networks are based on the star topology. In this article, a tree network adopted for the LoRa technology and a communication protocol are proposed to mitigate the energy consumption constraints. In the proposed network, the nodes are self-configured based on the LoRa physical link behavior and can act as relays to propagate data from other nodes. The analysis, design, and evaluation of the proposed architecture for large scale LoRa networks are presented in detail. With analytical studies, the energy consumption of the star and tree LoRa networks are compared. The presented analytical results can provide developers with effective guidelines for scalable design and optimization of LoRa networks. Further, the results are verified using simulation and experimental tests. Both simulation and experimental results confirm that the presented method improves the energy consumption of the entire IoT network significantly. As a result, the presented tree network can be deployed in various applications.

In this paper, we address the problem of ellipse recovery from blurred shape images. A shape image is a binary-valued (0/1) image in continuous-domain that represents one or multiple shapes. In general, the shapes can also be overlapping. We assume to observe the shape image through finitely many blurred samples, where the 2D blurring kernel is assumed to be known. The samples might also be noisy. Our goal is to detect and locate ellipses within the shape image. Our approach is based on representing an ellipse as the zero-level-set of a bivariate polynomial of degree 2. Indeed, similar to the theory of finite rate of innovation (FRI), we establish a set of linear equations (annihilation filter) between the image moments and the coefficients of the bivariate polynomial. For a single ellipse, we show that the image can be perfectly recovered from only 6 image moments (improving the bound in [Fatemi et al., 2016]). For multiple ellipses, instead of searching for a polynomial of higher degree, we locally search for single ellipses and apply a pooling technique to detect the ellipse. As we always search for a polynomial of degree 2, this approach is more robust against additive noise compared to the strategy of searching for a polynomial of higher degree (detecting multiple ellipses at the same time). Besides, this approach has the advantage of detecting ellipses even when they intersect and some parts of the boundaries are lost. Simulation results using both synthetic and real world images (red blood cells) confirm superiority of the performance of the proposed method against the existing techniques.

We investigate eigenvectors of rank-one deformations of random matrices$\boldsymbol B = \boldsymbol A + \theta \boldsymbol {uu}^{*}$in which$\boldsymbol A \in \mathbb R^{N \times N}$is a Wigner real symmetric random matrix,$\theta \in \mathbb R^{+}$, and$\boldsymbol u$is uniformly distributed on the unit sphere. It is well known that for$\theta > 1$the eigenvector associated with the largest eigenvalue of$\boldsymbol B$closely estimates$\boldsymbol u$asymptotically, while for$\theta < 1$the eigenvectors of$\boldsymbol B$are uninformative about$\boldsymbol u$. We examine$\mathcal O({1}/{N})$correlation of eigenvectors with$\boldsymbol u$before phase transition and show that eigenvectors with larger eigenvalue exhibit stronger alignment with deforming vector through an explicit inverse law${1}/{\theta ^{*} - x}$with$\theta ^{*}:= \theta + ({1}/{\theta })$. This distribution function will be shown to be the ordinary generating function of Chebyshev polynomials of the second kind. These polynomials form an orthogonal set with respect to the semicircle weighting function. This law is an increasing function in the support of semicircle law for eigenvalues$(-2\:,+2)$. Therefore, most of energy of the unknown deforming vector is concentrated in a$cN$-dimensional ($c < 1$) known subspace of$\boldsymbol B$. We use a combinatorial approach to prove the result. We also extend the result to constant rank-$r$deformations.

The Renyi's information dimension (RID) of an n-dimensional random vector (RV) is the average dimension of the vector when accounting for non-zero probability measures over lower-dimensional subsets. From an information-theoretical perspective, the RID can be interpreted as a measure of compressibility of a probability distribution. While the RID for continuous and discrete measures is well understood, the case of a discrete-continuous measures presents a number of interesting subtleties. In this paper, we investigate the RID for a class of multi-dimensional discrete-continuous random measures with singularities on affine lower dimensional subsets. This class of RVs, which we term affinely singular, arises from linear transformation of orthogonally singular RVs, that include RVs with singularities on affine subsets parallel to principal axes. We obtain the RID of affinely singular RVs and derive an upper bound for the RID of Lipschitz functions of orthogonally singular RVs. As an application of our results, we consider the example of a moving-average stochastic process with discrete-continuous excitation noise and obtain the RID for samples of this process. We also provide insight about the relationship between the block-average information dimension of the truncated samples, the minimum achievable compression rate, and other measures of compressibility for this process.

In this letter, we consider the problem of blind source separation under certain nonlinear mixing conditions using a deep learning approach. Conventionally, the separation of sources within linear mixtures is achieved by applying the independence property of the sources. In the nonlinear regime, however, this property is no longer sufficient. In this letter, we consider nonlinear mixing operators where the non-linearity could be fairly approximated using a Taylor series. Next, for solving the nonlinear BSS problem, we design an end-to-end recurrent neural network (RNN) that learns the inverse of the system, and ultimately separates the sources. For training the RNN, we employ a set of multi-variate polynomial functions to simulate the Taylor expansion of the nonlinear mixture. Numerical experiments show that the proposed method successfully separates the sources with a performance superior to the state of the art approaches.

The matrix decomposing into a sum of low-rank and sparse components has found extensive applications in many areas including video surveillance, computer vision, and medical imaging. In this paper, we propose a new algorithm for recovery of low rank and sparse components of a given matrix. We have also proved the convergence of the proposed algorithm. The simulation results with synthetic and real signals such as image and video signals indicate that the proposed algorithm has a better performance with lower run-time than the conventional methods.

With the dominance of digital imaging systems, we are often dealing with discrete-domain samples of an analog image. Due to physical limitations, all imaging devices apply a blurring kernel on the input image before taking samples to form the output pixels. In this paper, we focus on the reconstruction of binary shape images from few blurred samples. This problem has applications in medical imaging, shape processing, and image segmentation. Our method relies on representing the analog shape image in a discrete grid much finer than the sampling grid. We formulate the problem as the recovery of a rank r matrix that is formed by a Hankel structure on the pixels. We further propose efficient ADMM-based algorithms to recover the low-rank matrix in both noiseless and noisy settings. We also analytically investigate the number of required samples for successful recovery in the noiseless case. For this purpose, we study the problem in the random sampling framework, and show that with O(r log4(n1n2)) random samples (where the size of the image is assumed to be n1 x n2) we can guarantee the perfect reconstruction with high probability under mild conditions. We further prove the robustness of the proposed recovery in the noisy setting by showing that the reconstruction error in the noisy case is bounded when the input noise is bounded. Simulation results confirm that our proposed method outperform the conventional total variation minimization in the noiseless settings.

This work is about the total variation (TV) minimization which is used for recovering gradient-sparse signals from compressed measurements. Recent studies indicate that TV minimization exhibits a phase transition behavior from failure to success as the number of measurements increases. In fact, in large dimensions, TV minimization succeeds in recovering the gradient-sparse signal with high probability when the number of measurements exceeds a certain threshold; otherwise, it fails almost certainly. Obtaining a closed-form expression that approximates this threshold is a major challenge in this field and has not been appropriately addressed yet. In this work, we derive a tight lower-bound on this threshold in case of any random measurement matrix whose null space is distributed uniformly with respect to the Haar measure. In contrast to the conventional TV phase transition results that depend on the simple gradient-sparsity level, our bound is highly affected by generalized notions of gradient-sparsity. Our proposed bound is very close to the true phase transition of TV minimization confirmed by simulation results.

The detection of landmarks or patterns is of interest for extracting features in biological images. Hence, algorithms for finding these keypoints have been extensively investigated in the literature, and their localization and detection properties are well known. In this paper, we study the complementary topic of local orientation estimation, which has not received similar attention. Simply stated, the problem that we address is the following: estimate the angle of rotation of a pattern with steerable filters centered at the same location, where the image is corrupted by colored isotropic Gaussian noise. For this problem, we propose an estimator formulated as linear combinations of circular harmonics with given radial profiles. We prove that the proposed estimator is unbiased. This property allows us to use a statistical framework based on the Cramér--Rao lower bound (CRLB) to study the limits on the accuracy of the corresponding class of estimators. We aim at evaluating the performance of detection methods based on steerable filters in terms of angular accuracy (as a lower bound), while considering the connection to maximum likelihood estimation. Beyond the general results, we analyze the asymptotic behavior of the lower bound in terms of the order of steerablility and propose an optimal subset of components that minimizes the bound. We define a mechanism for selecting optimal subspaces of the span of the detectors. These are characterized by the most relevant angular frequencies. Finally, we project our template to the span of circular harmonics with given radial profiles and experimentally show that the prediction accuracy achieves the predicted CRLB. As an extension, we also consider steerable wavelet detectors.

In this letter, we consider the problem of recovering analysis-sparse signals from under-sampled measurements when some prior information about the support is available. We incorporate such information in the recovery stage by suitably tuning the weights in a weighted L1-analysis optimization problem. Indeed, we try to set the weights such that the method succeeds with minimum number of measurements. For this purpose, we exploit the upper-bound on the statistical dimension of a certain cone to determine the weights. Our numerical simulations confirm that the introduced method with tuned weights outperforms the standard L1-analysis technique.

We study the problem of reconstructing a block-sparse signal from compressively sampled measurements. In certain applications, in addition to the inherent block-sparse structure of the signal, some prior information about the block support, i.e., blocks containing non-zero elements, might be available. Although many block-sparse recovery algorithms have been investigated in the Bayesian framework, it is still unclear how to incorporate the information about the probability of occurrence into regularization-based block-sparse recovery in an optimal sense. In this letter, we bridge between these fields by the aid of a new concept in conic integral geometry. Specifically, we solve a weighted optimization problem when the prior distribution about the block support is available. Moreover, we obtain the unique weights that minimize the expected required number of measurements. Our simulations on both synthetic and real data confirm that these weights considerably decrease the required sample complexity.

The design of deterministic measurement matrices has been the focus of research in compressed sensing from the early stages. In particular, structured measurement matrices are of great interest as they could be efficiently stored. Our focus in this letter is on Toeplitz structure, which naturally arises in linear shift-invariant systems (convolution operator). We design complex-valued Toeplitz matrices with unit modulus elements that have small coherence. The complex phase of the matrix elements are determined by certain polynomials. We provide upper bounds for the coherence of the resulting matrix using tools from analytic number theory, namely, the Weyl sum theorem. Simulation results confirm that the proposed matrices perform similar to the Gaussian Toeplitz matrices of the same size.

Evaluating the statistical dimension is a common tool to determine the asymptotic phase transition in compressed sensing problems with Gaussian ensemble. Unfortunately, the exact evaluation of the statistical dimension is very difficult and it has become standard to replace it with an upper-bound. To ensure that this technique is suitable, [1] has introduced an upper-bound on the gap between the statistical dimension and its approximation. In this work, we first show that the error bound in [1] in some low-dimensional models such as total variation and ℓ1analysis minimization becomes poorly large. Next, we develop a new error bound which significantly improves the estimation gap compared to [1]. In particular, unlike the bound in [1] that fails in some settings with overcomplete dictionaries, our bound exhibits a decaying behavior in such cases.

One of the solutions proposed to reduce system cost and power consumption in massive multiple-input multiple-output (MIMO) systems is the use of extremely low-resolution data converters in radio-frequency (RF) chains. The resulting severe signal distortion calls for more sophisticated data detection algorithms. The near Maximum-Likelihood (ML) detection schemes proposed so far, either exhibit numerical instability issues at high SNRs or suffer from prohibitively high computational complexity. In this paper, we propose a modified near-ML detection algorithm for the one-bit quantized case that eliminates the numerical issues with the lowest complexity among similar algorithms. We also present a low-complexity VLSI architecture for the proposed algorithm. Finally, we demonstrate the FPGA implementation results of the proposed architecture and show that its complexity is similar to that of linear detectors, while significantly outperforms them from the symbol error rate (SER) performance perspective.

This letter considers the use of total variation (TV) minimization in the recovery of a given gradient sparse vector from Gaussian linear measurements. It has been shown in recent studies that there exists a sharp phase transition behavior in TV minimization for the number of measurements necessary to recover the signal in asymptotic regimes. The phase-transition curve specifies the boundary of success and failure of TV minimization for large number of measurements. It is a challenging task to obtain a theoretical bound that reflects this curve. In this letter, we present a novel upper bound that suitably approximates this curve and is asymptotically sharp. Numerical results show that our bound is closer to the empirical TV phase-transition curve than the previously known bound obtained by Kabanava.

The sparsity and compressibility of finite-dimensional signals are of great interest in fields, such as compressed sensing. The notion of compressibility is also extended to infinite sequences of independent identically distributed or ergodic random variables based on the observed error in their nonlinear k-term approximation. In this paper, we use the entropy measure to study the compressibility of continuous-domain innovation processes (alternatively known as white noise). Specifically, we define such a measure as the entropy limit of the doubly quantized (time and amplitude) process. This provides a tool to compare the compressibility of various innovation processes. It also allows us to identify an analogue of the concept of “entropy dimension" which was originally defined by Rényi for random variables. Particular attention is given to stable and impulsive Poisson innovation processes. Here, our results recognize Poisson innovations as the more compressible ones with an entropy measure far below that of stable innovations. While this result departs from the previous knowledge regarding the compressibility of impulsive Poisson laws compared with continuous fat-tailed distributions, our entropy measure ranks α-stable innovations according to their tail.

We study the pilot design problem for sparse channel estimation in OFDM systems where multiple channels are estimated at a single antenna receiver. Such design is applicable to downlink of massive-MIMO systems and also to scenarios where multiple users transmit to a base station at the same carrier frequency. In our design, we deviate from the conventional orthogonal pilot arrangements by assigning the same pilot subcarriers to all transmitters. In the proposed setting, the achieved improvement in spectral efficiency (by reducing pilot overhead) may come at the expense of a more challenging channel estimation block at the receiver. To address this challenge and distinguish between different signals that are arriving at the receiver at the same subcarrier, we propose to select pilot subcarriers through minimizing the coherence of the associated Fourier submatrix, as well as properly assigning different pilot values (complex numbers) to each individual transmitter. We demonstrate that if the channels are sparse enough in time domain, there are simple sparse recovery techniques to simultaneously estimate all the channels, although all transmitters share the same pilot subcarriers. Simulation results demonstrate that the proposed design outperforms existing methods in terms of both mean-square channel estimation error and bit error rate.

In this study, the authors consider the designing of a new set of uniquely decodable codes for uncoded synchronous overloaded code division multiple access for the number of codes exceeding the assigned code length. For the construction, the proposed recursive method at iteration‐ k generates a matrix that can be classified into k orthogonal subsets of different dimensions. Out of them, all besides the largest (binary Hadamard) one are ternary in nature. There resides an inbuilt twin tree structured cross‐correlation hierarchy that facilitates an advantageous balance between the auto and intergroup cross‐correlation for the signatures in a subset. This opportunity is further leveraged by the proposed multi‐stage detector to maintain the uniquely decodable (errorless) nature of the matrices for noiseless transmission. The simple logic of matched filtering serving as the basic designing block of the decoder provides an enormous saving over the complexity of optimum maximum likelihood decoder. For the noisy channel, the authors derive the theoretical expression of the average bit error rate for the individual subset. Moreover, the authors explain the role of the two factors (cardinality of the subset, and net level of interference) in being responsible for the non‐uniformity in the order of their error performance.

Continuous-domain visual signals are usually captured as discrete (digital) images. This operation is not invertible in general, in the sense that the continuous-domain signal cannot be exactly reconstructed based on the discrete image, unless it satisfies certain constraints (e.g., bandlimitedness). In this paper, we study the problem of recovering shape images with smooth boundaries from a set of samples. Thus, the reconstructed image is constrained to regenerate the same samples (consistency), as well as forming a shape (bilevel) image. We initially formulate the reconstruction technique by minimizing the shape perimeter over the set of consistent binary shapes. Next, we relax the non-convex shape constraint to transform the problem into minimizing the total variation over consistent non-negative-valued images. We also introduce a requirement (called reducibility) that guarantees equivalence between the two problems. We illustrate that the reducibility property effectively sets a requirement on the minimum sampling density. We also evaluate the performance of the relaxed alternative in various numerical experiments.

Overloaded code division multiple access being the only means of the capacity extension for conventional code division multiple access accommodates more number of signatures than the spreading gain. Recently, ternary Signature Matrices with Orthogonal Subsets (SMOS) has been proposed, where the capacity maximization is 200%. The proposed multi-user detector using matched filter exploits the twin tree hierarchy of correlation among the subsets to guarantee the errorless recovery. In this paper, we feature the non-ternary version of SMOS (i.e., 2k-ary SMOS) of same capacity, where the binary alphabets in all the k constituent (orthogonal) subsets are unique. Unlike ternary, the tree hierarchy for 2k-ary SMOS is non-uniform. However, the errorless detection of the multi-user detector remains undeviated. For noisy transmission, simulation results show the error performance of the right child for each subset of 2k-ary to be significantly improved over the left. The optimality of the right child of the largest (Hadamard) subset is also discovered. At higher loading, for larger and smaller subsets the superiority is reported for the 2k-ary and ternary, respectively, and the counter-intuitive deviations observed for the lower loading scenarios are logically explained. For the overall capacity maximization being 150%, superiority is featured by the 2k-ary, but beyond, it becomes a conditional entity. Copyright © 2016 John Wiley & Sons, Ltd.

We adopt an innovation-driven framework and investigate the sparse/compressible distributions obtained by linearly measuring or expanding continuous-domain stochastic models. Starting from the first principles, we show that all such distributions are necessarily infinitely divisible. This property is satisfied by many distributions used in statistical learning, such as Gaussian, Laplace, and a wide range of fat-tailed distributions, such as student's-t and α-stable laws. However, it excludes some popular distributions used in compressed sensing, such as the Bernoulli-Gaussian distribution and distributions, that decay like exp (-O(|x|p)) for 1p<; 2. We further explore the implications of infinite divisibility on distributions and conclude that tail decay and unimodality are preserved by all linear functionals of the same continuous-domain process. We explain how these results help in distinguishing suitable variational techniques for statistically solving inverse problems like denoising.

This paper is devoted to the characterization of an extended family of continuous-time autoregressive moving average (CARMA) processes that are solutions of stochastic differential equations driven by white Lévy innovations. These are completely specified by: 1) a set of poles and zeros that fixes their correlation structure and 2) a canonical infinitely divisible probability distribution that controls their degree of sparsity (with the Gaussian model corresponding to the least sparse scenario). The generalized CARMA processes are either stationary or nonstationary, depending on the location of the poles in the complex plane. The most basic nonstationary representatives (with a single pole at the origin) are the Lévy processes, which are the non-Gaussian counterparts of Brownian motion. We focus on the general analog-to-discrete conversion problem and introduce a novel spline-based formalism that greatly simplifies the derivation of the correlation properties and joint probability distributions of the discrete versions of these processes. We also rely on the concept of generalized increment process, which suppresses all long range dependencies, to specify an equivalent discrete-domain innovation model. A crucial ingredient is the existence of a minimally supported function associated with the whitening operator L; this B-spline, which is fundamental to our formulation, appears in most of our formulas, both at the level of the correlation and the characteristic function. We make use of these discrete-domain results to numerically generate illustrative examples of sparse signals that are consistent with the continuous-domain model.

Bayesian estimation problems involving Gaussian distributions often result in linear estimation techniques. Nevertheless, there are no general statements as to whether the linearity of the Bayesian estimator is restricted to the Gaussian case. The two common strategies for non-Gaussian models are either finding the best linear estimator or numerically evaluating the Bayesian estimator by Monte Carlo methods. In this paper, we focus on Bayesian interpolation of non-Gaussian first-order autoregressive (AR) processes where the driving innovation can admit any symmetric infinitely divisible distribution characterized by the Lévy-Khintchine representation theorem. We redefine the Bayesian estimation problem in the Fourier domain with the help of characteristic forms. By providing analytic expressions, we show that the optimal interpolator is linear for all symmetric -stable distributions. The Bayesian interpolator can be expressed in a convolutive form where the kernel is described in terms of exponential splines. We also show that the limiting case of Lévy-type AR(1) processes, the system of which has a pole at the origin, always corresponds to a linear Bayesian interpolator made of a piecewise linear spline, irrespective of the innovation distribution. Finally, we show the two mentioned cases to be the only ones within the family for which the Bayesian interpolator is linear.

We investigate the problem of the optimal reconstruction of a generalized Poisson process from its noisy samples. The process is known to have a finite rate of innovation since it is generated by a random stream of Diracs with a finite average number of impulses per unit interval. We formulate the recovery problem in a Bayesian framework and explicitly derive the joint probability density function (pdf) of the sampled signal. We compare the performance of the optimal Minimum Mean Square Error (MMSE) estimator with common regularization techniques such as ℓ1and Log penalty functions. The simulation results indicate that, under certain conditions, the regularization techniques can achieve a performance close to the MMSE method.

Many recent algorithms for sparse signal recovery can be interpreted as maximum-a-posteriori (MAP) estimators relying on some specific priors. From this Bayesian perspective, state-of-the-art methods based on discrete-gradient regularizers, such as total-variation (TV) minimization, implicitly assume the signals to be sampled instances of Lévy processes with independent Laplace-distributed increments. By extending the concept to more general Lévy processes, we propose an efficient minimum-mean-squared error (MMSE) estimation method based on message-passing algorithms on factor graphs. The resulting algorithm can be used to benchmark the performance of the existing or design new algorithms for the recovery of sparse signals.

Motivated by the analog nature of real-world signals, we investigate continuous-time random processes. For this purpose, we consider the stochastic processes that can be whitened by linear transformations and we show that the distribution of their samples is necessarily infinitely divisible. As a consequence, such a modeling rules out the Bernoulli-Gaussian distribution since we are able to show in this paper that it is not infinitely divisible. In other words, while the Bernoulli-Gaussian distribution is among the most studied priors for modeling sparse signals, it cannot be associated with any continuous-time stochastic process. Instead, we propose to adapt the priors that correspond to the increments of compound Poisson processes, which are both sparse and infinitely divisible.

We introduce a new method for adaptive one-bit quantization of linear measurements and propose an algorithm for the recovery of signals based on generalized approximate message passing (GAMP). Our method exploits the prior statistical information on the signal for estimating the minimum-mean-squared error solution from one-bit measurements. Our approach allows the one-bit quantizer to use thresholds on the real line. Given the previous measurements, each new threshold is selected so as to partition the consistent region along its centroid computed by GAMP. We demonstrate that the proposed adaptive-quantization scheme with GAMP reconstruction greatly improves the performance of signal and image recovery from one-bit measurements.

The problem of extracting low-dimensional structure from high-dimensional data arises in many applications such as machine learning, statistical pattern recognition, wireless sensor networks, and data compression. If the data is restricted to a lower dimensional subspace, then simple algorithms using linear projections can find the subspace and consequently estimate its dimensionality. However, if the data lies on a low-dimensional but nonlinear space (e.g., manifolds), then its structure may be highly nonlinear and, hence, linear methods are doomed to fail. In this paper, we introduce a new technique for dimensionality reduction based on point-wise operators. More precisely, let be a matrix of rank and assume that the matrix is generated by taking the elements of to some real power . In this paper, we show that based on the values of the data matrix , one can estimate the value and, therefore, the underlying low-rank matrix ; i.e., we are reducing the dimensionality of by using point-wise operators. Moreover, the estimation algorithm does not need to know the rank of . We also provide bounds on the quality of the approximation and validate the stability of the proposed algorithm with simulations in noisy environments.

In this paper, we establish the connection between the Orthogonal Optical Codes (OOC) and binary compressed sensing matrices. We also introduce deterministic bipolar m × n RIP fulfilling ±1 matrices of orderksuch thatm≤O(k(log2n)( log2k)/( ln log2k)). The columns of these matrices are binary BCH code vectors where the zeros are replaced by -1. Since the RIP is established by means of coherence, the simple greedy algorithms such as Matching Pursuit are able to recover the sparse solution from the noiseless samples. Due to the cyclic property of the BCH codes, we show that the FFT algorithm can be employed in the reconstruction methods to considerably reduce the computational complexity. In addition, we combine the binary and bipolar matrices to form ternary sensing matrices ({0,1,-1} elements) that satisfy the RIP condition.

Among the many attacks against watermarked data, the gain attack is less supported with countermeasures. The effectiveness of this attack becomes more evident in quantization-based embedding algorithms such as Dither Modulation (DM). In this paper, the general solution for both block and sample type DM schemes that are robust against gain attacks is considered. Among the solutions, we concentrate on a subclass of the algorithms which are insensitive to additive noise attacks; i.e., we introduce watermarking schemes which are both robust against gain and additive noise attacks. The simulation results confirm the desired performance of the final algorithm against these attacks while outperform other gain invariant schemes.