Electroencephalography (EEG) signals record the electrical activity of the brain and have significant applications in neuroscience and medicine. However, accurately reconstructing EEG signals has been a challenge due to potential signal missing and noise interference during signal acquisition. The paper exploits the underlying structure of EEG signals and presents an efficient method for reconstructing EEG signals based on local graph signal smoothness (LGS-based). Firstly, we introduce the concept of local graph signal smoothness according to distinct functional areas of the cerebral cortex. Then, considering the graph that does not properly represent similar relationships between signals will have a negative impact on the reconstruction performance, we propose a joint graph learning and EEG signal reconstruction optimization method. Since it is not jointly convex, we utilize the alternating direction method of multipliers (ADMM) to solve it. In experiments, it is shown that the proposed LGS-based method outperforms benchmark methods in EEG signal reconstruction. Additionally, the proposed method achieves a higher signal-to-noise ratio (SNR) as well as a smaller normalized mean square error (RMSE).

Graph prompt tuning has achieved significant success for its ability to effectively adapt pre-trained graph neural networks to various downstream tasks. However, the pre-trained models may learn discriminatory representation due to the inherent prejudice in graph-structured data. Existing graph prompt tuning overlooks such unfairness, leading to biased outputs towards certain demographic groups determined by sensitive attributes such as gender, age, and political ideology. To overcome this limitation, we propose a fairness-aware graph prompt tuning method to promote fairness while enhancing the generality of any pre-trained GNNs (named FPrompt). FPrompt introduces hybrid graph prompts to augment counterfactual data while aligning the pre-training and downstream tasks. It also applies edge modification to increase sensitivity heterophily. We provide a two-fold theoretical analysis: first, we demonstrate that FPrompt possesses universal capabilities in handling pre-trained GNN models across various pre-training strategies, ensuring its adaptability in different scenarios. Second, we show that FPrompt effectively reduces the upper bound of generalized statistical parity, thereby mitigating the bias of pre-trained models. Extensive experiments demonstrate that FPrompt outperforms baseline models in both accuracy and fairness (33%) on benchmark datasets. Additionally, we introduce a new benchmark for transferable evaluation, showing that FPrompt achieves state-of-the-art generalization performance.

Recently, textual information has been proven to positively affect recommendation systems. However, most of the existing methods only focus on representation learning of textual information in ratings, while potential selection bias induced by the textual information is ignored. In this work, we propose a novel and general self-adaptive module, the self-adaptive attention module (SAM), which adjusts the selection bias by capturing contextual information based on its representation. This module can be embedded into recommendation systems that contain learning components of contextual information. Experimental results on three real-world datasets demonstrate the effectiveness of our proposal, and the state-of-the-art models with SAM significantly outperform the original ones.

Sparse phase retrieval aims to reconstruct an $n$-dimensional $k$-sparse signal from its phaseless measurements. For most of the existing reconstruction algorithms, their sampling complexity is known to be dominated by the initialization stage. In this paper, in order to improve the sampling complexity for initialization, we propose a novel method termed exponential spectral pursuit (ESP). Theoretically, our method offers a tighter bound of sampling complexity compared to the state-of-the-art ones, such as the truncated power method. Moreover, it empirically outperforms the existing initialization methods for sparse phase retrieval.

Collective matrix completion (CMC) offers a straightforward approach to dealing with data with entries from various sources. Benefiting from the joint structure in the collective matrix, CMC often achieves fast convergence. However, since CMC conducts matrix-level operations, it neglects the entry-wise information that can potentially be very useful for matrix completion. In this paper, to capture the entry-wise information, we propose a method called graph collective matrix completion (GCoMC). Specifically, our method integrates a graph pattern extraction module into CMC via a relational graph convolutional network. Experiments on simulated and real-world datasets show that our method significantly outperforms some existing counterparts.

In recent years, phase retrieval has received much attention in statistics, applied mathematics and optical engineering. In this paper, we propose an efficient algorithm, termed Subspace Phase Retrieval (SPR), which can accurately recover ann-dimensionalk-sparse complex-valued signal x given its Ω(k2logn) magnitude-only Gaussian samples if the minimum nonzero entry of x satisfies |xmin| = Ω(∥x∥/ √k). Furthermore, if the energy sum of the most significant √kelements in x is comparable to ∥x∥2, the SPR algorithm can exactly recover x with Ω(klogn) magnitude-only samples, which attains the information-theoretic sampling complexity for sparse phase retrieval. Numerical Experiments demonstrate that the proposed algorithm achieves the state-of-the-art reconstruction performance compared to existing ones.

Tensor completion aims at filling the missing or unobserved en-tries based on partially observed tensors. However, utilization of the observed tensors often raises serious privacy concerns in many practical scenarios. To address this issue, we propose a solid and unified framework that contains several approaches for applying differential privacy to the two most widely used tensor decomposition methods: i) CANDECOMP/PARAFAC and ii) Tucker decompositions. For each approach, we establish a rigorous privacy guarantee and meanwhile evaluate the privacy-accuracy trade-off. Experiments on synthetic datasets demonstrate that our proposal achieves high accuracy for tensor completion while ensuring strong privacy protections.

Compressed sensing (CS) aims to recover a high-dimensional signal with structural priors from its low-dimensional linear measurements. Inspired by the huge success of deep neural networks in modeling the priors of natural signals, generative neural networks have been recently used to replace the hand-crafted structural priors in CS. However, the reconstruction capability of the generative model is fundamentally limited by the range of its generator, typically a small subset of the signal space of interest. To break this bottleneck and thus reconstruct those out-of-range signals, this paper presents a novel method called CS-BGM that can effectively expands the range of generator. Specifically, CS-BGM introduces uncertainties to the latent variable and parameters of the generator, while adopting the variational inference (VI) and maximum a posteriori (MAP) to infer them. Theoretical analysis demonstrates that expanding the range of generators is necessary for reducing the reconstruction error in generative CS. Extensive experiments show a consistent improvement of CS-BGM over the baselines.

Recent years, local differential privacy (LDP) has been adopted by many web service providers like Google [23], Apple [33] and Microsoft [15] to collect and analyse users’ data privately. In this paper, we consider the problem of discrete distribution estimation under local differential privacy constraints. Distribution estimation is one of the most fundamental estimation problems, which is widely studied in both non-private and private settings. In the local model, private mechanisms with provably optimal sample complexity are known. However, they are optimal only in the worst-case sense; their sample complexity is proportional to the size of the entire universe, which could be huge in practice. In this paper, we consider sparse or approximately sparse (e.g. highly skewed) distribution, and show that the number of samples needed could be significantly reduced. This problem has been studied recently [1], but they only consider strict sparse distributions and the high privacy regime. We propose new privatization mechanisms based on compressive sensing. Our methods work for approximately sparse distributions and medium privacy, and have optimal sample and communication complexity.

Over the years, quantifying the similarity of nodes has been a hot topic in network science, yet little has been known about the distribution of node-similarity. In this paper, we consider a typical measure of node-similarity called the common neighbor based similarity (CNS). By means of the generating function, we propose a general framework for calculating the CNS distributions of node sets in various networks. Particularly, we show that for the Erdös-Rényi random network, the CNS distribution of node sets of any size obeys the Poisson law. Furthermore, we connect the node-similarity distribution to the link prediction problem, and derive analytical solutions for two key evaluation metrics: i) precision and ii) area under the receiver operating characteristic curve (AUC). We also use the similarity distributions to optimize link prediction by i) deriving the expected prediction accuracy of similarity scores and ii) providing the optimal prediction priority of unconnected node pairs. Simulation results confirm our theoretical findings and also validate the proposed tools in evaluating and optimizing link prediction.

Ghost imaging via sparsity constraint (GISC) can recover objects from the intensity fluctuation of light fields at a sampling rate far below the Nyquist rate. However, its imaging quality may degrade severely when the coherence of sampling matrices is large. To deal with this issue, we propose an efficient recovery algorithm for GISC called the preconditioned multiple orthogonal least squares (PmOLS). Our algorithm consists of two major parts: i) the pseudo-inverse preconditioning (PIP) method refining the coherence of sampling matrices and ii) the multiple orthogonal least squares (mOLS) algorithm recovering the objects. Theoretical analysis shows that PmOLS recovers any n-dimensional K-sparse signal from m random linear samples of the signal with probability exceeding 1-3n2e-cm/K2. Simulations and experiments demonstrate that PmOLS has competitive imaging quality compared to the state-of-the-art approaches.

In this paper, we put forth a new joint sparse recovery algorithm called signal space matching pursuit (SSMP). The key idea of the proposed SSMP algorithm is to sequentially investigate the support of jointly sparse vectors to minimize the subspace distance to the residual space. Our performance guarantee analysis indicates that SSMP accurately reconstructs any row K-sparse matrix of rank r in the full row rank scenario if the sampling matrix A satisfies krank(A) ≥ K+1, which meets the fundamental minimum requirement on A to ensure exact recovery. We also show that SSMP guarantees exact reconstruction in at most K - r + [r/L] iterations, provided that A satisfies the restricted isometry property (RIP) of order L(K - r) + r + 1 %/L with δL(K-r)+r+1[7.8K]≤ 0.155. Furthermore, we show that under a suitable RIP condition, the reconstruction error of SSMP is upper bounded by a constant multiple of the noise power, which demonstrates the robustness of SSMP to measurement noise. Finally, from extensive numerical experiments, we show that SSMP outperforms conventional joint sparse recovery algorithms both in noiseless and noisy scenarios.

We investigate the weighted-sum distortion minimization problem in transmitting two correlated Gaussian sources over Gaussian channels using two energy harvesting nodes. To this end, we develop off-line and online power control policies to optimize the transmit power of the two nodes. In the off-line case, we cast the problem as a convex optimization and investigate the structure of the optimal solution. We also develop a generalized waterfilling-based power allocation algorithm to obtain the optimal solution efficiently. For the online case, we quantify the distortion of the system using a cost function and show that the expected cost equals the expected weighted-sum distortion. Based on Banach's fixed point theorem, we further propose a geometrically converging algorithm to find the minimum cost via simple iterations. Simulation results show that our online power control outperforms the greedy power control where each node uses all the available energy in each slot and also performs close to that of the proposed off-line power control. Moreover, the performance of our off-line power control almost coincides with the performance limit of the system.

Support recovery of sparse signals from noisy measurements with orthogonal matching pursuit (OMP) has been extensively studied in the literature. In this paper, we show that for any K-sparse signal x, if the sensing matrix A satisfies the restricted isometry property (RIP) of order K+1 with restricted isometry constant (RIC) δK+1K+1since for any given positive integer K ≥ 2 and any 1/√K+1 ≤ tK+1= t for which OMP may fail to recover the signal x in K iterations. Moreover, the constraint on the minimum magnitude of the nonzero elements of x is weaker than existing results.

We consider cluster-based routing protocols for energy harvesting wireless sensor networks. Since the energy harvesting process does not match the real energy demand, sensor nodes suffer from occasional energy shortages, especially when they serve as cluster head (CH) nodes. To address this problem, we propose a cluster-based routing protocol referred to as distance-and-energy-aware routing with energy reservation (DEARER). The DEARER protocol encourages nodes with high energy-arrival rate or being close to the sink to serve as CH nodes. Also, DEARER allows non-CH nodes to reserve a portion of the harvested energy for future use. In doing so, the DEARER selects “enabler” nodes as CH nodes and provides them with more energy, thereby mitigating the energy shortage events at CH nodes. By theoretical analysis and numerical experiments, we demonstrate that the DEARER protocol outperforms direct transmission and also approaches the genie-aided routing, where CH nodes are selected based on the real-time energy information of each node.

In this paper, we propose an algorithm referred to as multipath matching pursuit (MMP) that investigates multiple promising candidates to recover sparse signals from compressed measurements. Our method is inspired by the fact that the problem to find the candidate that minimizes the residual is readily modeled as a combinatoric tree search problem and the greedy search strategy is a good fit for solving this problem. In the empirical results as well as the restricted isometry property-based performance guarantee, we show that the proposed MMP algorithm is effective in reconstructing original sparse signals for both noiseless and noisy scenarios.

In this paper, we propose a sparse recovery algorithm, termed multiple path matching pursuit (MMP), that improves the recovery performance of sparse signals. By investigating the multiple paths and then choosing the most promising path in the final moment, the MMP algorithm improves the chance of finding the true support and therefore enhances the recovery performance. From the restricted isometry property (RIP) analysis, we show that the MMP algorithm can perfectly reconstruct any K-sparse (K >1) signals,√provided that the sensing matrix satisfies RIP with δK+L< √ L/√ K +3√ L. We demonstrate by empirical simulations that the MMP algorithm is very competitive in both noisy and noiseless scenarios.

Recent works on ad hoc network study have shown that achievable throughput can be made to scale linearly with the number of receive antennas even if the transmitter has only a single antenna. In this paper, we propose a non-parametric linear minimum mean square error (MMSE) receiver for achieving further gain in performance when the channel state information at receiver (CSIR) of interferers is imperfect. The key feature to make our approach effective is to exploit the autocorrelation of the received signal. In fact, by incorporating the desired channel information on top of the observations including interference and noise only, the proposed method achieves large fraction of the optimal MMSE transmission capacity without transmission rate loss. Simulation results on the realistic ad hoc network system show that the proposed non-parametric linear MMSE receiver brings substantial performance gain over existing multiple receive antenna algorithms.