Abstract. One-bit quantized measurements are commonly encountered in resource-constrained imaging applications such as medical imaging and satellite remote sensing. Although stable signal reconstruction from noise-free one-bit measurements has been widely demonstrated, noise in practical data acquisition systems often leads to unknown sign flips, significantly increasing the difficulty of accurate recovery. While numerous robust methods have been developed for signal reconstruction from noisy one-bit measurements, most of them necessitate prior knowledge of the number of sign flips, which is typically unavailable in practice. In this paper, we propose two novel optimization models based on continuous approximation functions (CAFs) of the sign function. The first model employs the quadratic loss function, specifically designed for scenarios with low sign flipping ratios, while the second incorporates a Hybrid Ordinary-Welsch (HOW) loss function, yielding enhanced robustness under higher flipping ratios without requiring prior knowledge. Then, we propose two algorithmic frameworks, OBCSA_CAF and OBCSA_CAF_HOW, to solve the respective models, and prove that both algorithms generate convergent sequences of objective function values and subsequences that, with high probability, converge to specific accumulation points. Extensive simulations demonstrate the superior performance of our methods over the state-of-the-art algorithms in terms of signal-to-noise ratio (SNR), rate of support recovery, Hamming error, and Hamming distance. In particular, OBCSA_CAF achieves 0.5–4 dB gains in SNR and [Formula: see text]–[Formula: see text] improvements in support recovery rate at low flipping ratios, whereas OBCSA_CAF_HOW yields 2–6.7 dB gains and [Formula: see text]–[Formula: see text] improvements, respectively, under high flipping ratios. Experiments on the MNIST and CIFAR-10 datasets further illustrate the superior performance of our methods in image reconstruction.

Detecting the integer parameter vector in a box-constrained linear model with additive Gaussian noise arises from many applications. The maximum likelihood (ML) detector detects the integer parameter vector by solving a Box-constrained Integer Least Squares (BILS) problem and achieves the highest success probability (i.e., the probability that the detected integer vector equals the original integer vector). However, due to the high complexity of the ML detector, the Babai detector is frequently used to approximate solutions to the BILS problem, especially in time-constrained applications. Considering the success probability achieved by existing Babai detector frameworks is not always satisfying, this paper focuses on proposing a fast block-based Babai detector framework within polynomial complexity to narrow the gap to the ML detector. Unlike element-wise Babai detectors, the proposed method partitions the model matrix into blocks and applies the appropriately sized ML detector to each block. Theoretical analysis shows that the success probability of the block-based Babai detector increases with the block size and therefore is better than the Babai detector. To further improve the success probability, an extended block-based Babai detector is proposed with a reasonable increase in complexity. Simulation results illustrate the theoretical findings and indicate that the proposed detectors achieve a better trade-off between the success probability and complexity compared with conventional Zero-Forcing (ZF), Successive Interference Cancellation (SIC)/Babai detectors, as well as the generalized Babai detector proposed by Chang et al.. For example, in a 16 × 16 MIMO system with 16-QAM modulation, the (extedned) block-based Babai detector can improve the success probability by 5.3% (8.7%) at SNR = 15dB and achieve a gain of approximately 1.5 dB (2 dB) at a BER of 10−3, compared with Chang et al.’s generalized Babai detector, while requiring only 45.1% (57.9%) of the computational complexity on average over the tested SNR range.

Abstract. The orthogonal matching pursuit (OMP) algorithm, known for its exceptional ability to reconstruct sparse signals, is a widely employed algorithm in compressed sensing. Numerous studies have provided theoretical analyses supporting its capability for achieving exact recovery. However, when applied to large-scale sparse signal recovery, the OMP algorithm incurs substantial computational overhead, leading to prolonged running time. To address this challenge, we design a Randomized OMP with Adaptive Partial Selection (AROMP) algorithm to mitigate computational overhead and reduce runtime. The novelty of the AROMP algorithm lies in its utilization of a randomized index selection method rather than a greedy approach to select the index in each iteration. Subsequently, we theoretically characterize the gap between AROMP and OMP for exactly recovering an [Formula: see text]-sparse signal and show that the gap decreases as the number of comparisons [Formula: see text] increases, sparsity [Formula: see text] decreases, or signal dimension [Formula: see text] decreases. As [Formula: see text] approaches [Formula: see text], the gap between AROMP and OMP tends to 0. The experimental results substantiate that our proposed method significantly reduces running time while maintaining satisfactory accuracy in sparse signal recovery, face recognition tasks, and image reconstruction tasks.

Several existing works have revealed the effectiveness of arctangent-type penalties in exploiting sparsity for compressed sensing. However, addressing the subproblems associated with the arctangent penalty incurs considerable computational cost. Aiming to reduce complexity, we derive the closed-form proximity operator of an arctangent penalty, which is expressed as hyperbolic functions of sine and cosine in this paper. Accordingly, a computationally-efficient arctangent regularization iterative thresholding (ARIT) algorithm for sparse approximation is proposed. Furthermore, we theoretically prove that under certain conditions, the ARIT algorithm converges to a local minimizer of the arctangent regularization problem with an eventually linear convergence. Extensive experiments are conducted to compare our scheme with conventional iterative thresholding algorithms, demonstrating the former superiority in terms of the probability of successful recovery, rate of support recovery, phase transition, and robustness to noise.

Federated learning faces challenges associated with privacy breaches, client communication efficiency, stragglers’ effect, and heterogeneity. To address these challenges, this paper reformulates the optimal client selection problem as a sparse optimization task, proposes a secure and efficient optimal client selection method for federated learning, named secure orthogonal matching pursuit federated learning (SecOMPFL). Therein, we first introduce a method to identify correlations in the local model parameters of participating clients, addressing the issue of duplicated client contributions highlighted in recent literature. Next, we establish a secure variant of the OMP algorithm in compressed sensing using secure multiparty computation and propose a novel secure aggregation protocol. This protocol enhances the global model’s convergence rate through sparse optimization techniques while maintaining privacy and security. It relies entirely on the local model parameters as inputs, minimizing client communication requirements. We also devise a client sampling strategy without requiring additional communication, resolving the bottleneck encountered by the optimal client selection policy. Finally, we introduce a strict yet inclusive straggler penalty strategy to minimize the impact of stragglers. Theoretical analysis confirms the security and convergence of SecOMPFL, highlighting its resilience to stragglers’ effect and systematic/statistical heterogeneity with high client communication efficiency. Numerical experiments were conducted to compare the convergence rate and client communication efficiency of SecOMPFL with those of FedAvg, FOLB, and BN2. These experiments used natural and synthetic with statistical heterogeneity datasets, considering varying numbers of clients and client sampling scales. The results demonstrate that SecOMPFL achieves a competitive convergence rate, with communication overhead 39.96% lower than that of FOLB and 28.44% lower than that of BN2. Furthermore, SecOMPFL shows good resilience to statistical heterogeneity.

In-context learning, a paradigm bridging the gap between pre-training and fine-tuning, has demonstrated high efficacy in several NLP tasks, especially in few-shot settings. Despite being widely applied, in-context learning is vulnerable to malicious attacks. In this work, we raise security concerns regarding this paradigm. Our studies demonstrate that an attacker can manipulate the behavior of large language models by poisoning the demonstration context, without the need for fine-tuning the model. Specifically, we design a new backdoor attack method, named ICLAttack, to target large language models based on in-context learning. Our method encompasses two types of attacks: poisoning demonstration examples and poisoning demonstration prompts, which can make models behave in alignment with predefined intentions. ICLAttack does not require additional fine-tuning to implant a backdoor, thus preserving the model’s generality. Furthermore, the poisoned examples are correctly labeled, enhancing the natural stealth of our attack method. Extensive experimental results across several language models, ranging in size from 1.3B to 180B parameters, demonstrate the effectiveness of our attack method, exemplified by a high average attack success rate of 95.0% across the three datasets on OPT models.

In this work, we derive the proximity operator of an arctangent penalty, which is expressed using hyperbolic functions of sine and cosine. This penalty is then applied to sparse signal recovery, and an efficient arctangent regularization iterative thresholding (ARIT) algorithm is proposed, offering closed-form solutions for the subproblems associated with the arctangent penalty. Extensive experiments are conducted to compare the performance of ARIT with several existing iterative thresholding algorithms, and the results demonstrate that our algorithm achieves the best overall performance in terms of the probability of successful recovery, phase transition and running time.

Affine frequency division multiplexing (AFDM) is an emerging multicarrier waveform that offers a potential solution for achieving reliable communications over time-varying channels. This paper proposes two maximum-likelihood (ML) estimators of symbol time offset and carrier frequency offset for AFDM systems. One is called joint ML estimator, which evaluates the arrival time and carrier frequency offset by comparing the correlations of samples. Moreover, we propose the other so-called stepwise ML estimator to reduce the complexity. Both proposed estimators exploit the redundant information contained within the chirp-periodic prefix inherent in AFDM symbols, thus dispensing with any additional pilots. To further mitigate the intercarrier interference resulting from the residual frequency offset, we design a mirror-mapping-based scheme for AFDM systems. Numerical results verify the effectiveness of the proposed time and carrier frequency offset estimation criteria and the mirror-mapping-based modulation for AFDM systems.

Sparse signal recovery arises from many applications. However, deterministic algorithms often require significant time, especially for large-scale systems. Hence, stochastic algorithms like the Stochastic Iterative Hard Thresholding Algorithm (StoIHT) were proposed to address large-scale problems. In this letter, we propose using the stochastic Polyak step size method to design step sizes and provide theoretical convergence analysis. Experimental results suggest that our algorithm demonstrates comparable performance to other stochastic algorithms in sparse signal recovery and image reconstruction with faster convergence.

Despite being widely applied, pre-trained language models have been proven vulnerable to backdoor attacks. Backdoor attacks are designed to introduce targeted vulnerabilities into models by poisoning a subset of training samples through trigger injection and label modification. Traditional textual backdoor attacks suffer several flaws: the triggers lead to abnormal natural language expressions, and poisoned sample labels are mistakenly labeled. These flaws reduce the stealthiness of the attack and can be easily detected by defense models. In this study, we introduce Cbat, a novel and efficient method to perform clean-label backdoor attack with text style, which does not require external trigger, and the poisoned samples are correctly labeled. Specifically, we develop a sentence rewriting model by leveraging the powerful few-shot learning capability of prompt tuning to generate clean label poisoned samples. Cbat then injects text style as an abstract trigger into the victim model through poisoned samples. We also introduce an algorithm for defending against backdoor attacks, named CbatD, which effectively erases the poisoned samples by locating the lowest training loss and calculating feature relevance. The experiments on text classification tasks demonstrate that our Cbat and CbatD show overall competitive performance in textual backdoor attack and defense. It is noteworthy that Cbat attained leading results in the clean-label backdoor attack benchmark without triggers.

This paper delves into the challenges of spread spectrum (SS) watermarking extraction, considering both reference-free and referential extraction scenarios, within the framework of lattice decoding. The orthogonality of carriers plays a crucial role in the accuracy of extraction, impacting the bit error rate (BER). When carriers lack sufficient orthogonality, conventional reference-free extraction methods such as multi-carrier iterative generalized least-squares (M-IGLS) and referential extraction techniques like MMSE-based schemes encounter performance degradation, posing difficulties in accurately recovering hidden data at the receiver end. To address these challenges, we propose two novel SS watermarking extraction approaches by integrating precise lattice decoding algorithms. Firstly, we introduce the highly accurate yet computationally efficient successive interference cancellation (SIC) algorithm to augment M-IGLS, resulting in a new method termed multi-carrier iterative successive interference cancellation (M-ISIC). Secondly, we adapt the near-optimal sphere decoding (SD) technique for referential extraction in SS watermarking. Theoretical analysis and experimental simulations showcase that our proposed M-ISIC and SD methods outperform M-IGLS and MMSE-based detectors, particularly in scenarios where carrier orthogonality is limited, achieving lower BER. Our code is available athttps://github.com/shx-lyu/M_ISIC.

In this paper, a novel amplitude phase shift keying (APSK) modulation scheme for cooperative backscatter communications aided by a reconfigurable intelligent surface (RIS-CBC) is presented, according to which a passive or an active RIS is configured to modulate backscatter information onto unmodulated or PSK-modulated signals impinging on its panel via APSK. In passive RIS-CBC-APSK, the backscatter information is conveyed through the number of RIS reflecting elements being in the ON state and their phase shift values, whereas, in active RIS-CBC-APSK, this information is embedded through the number of RIS elements being in the active mode as well as the phase shift values of all elements. By using the optimal APSK constellation to ensure that reflected signals from the RIS undergo APSK modulation, a bit-mapping mechanism is developed. Assuming maximum-likelihood detection, we also present closed-form upper bounds for the symbol error rate (SER) performance for both proposed passive and active RIS-CBC-APSK schemes over Rician fading channels. In addition, we devise a low-complexity detector that can achieve flexible trade-offs between performance and complexity. Finally, we extend RIS-CBC-APSK to multiple-input single-output scenarios and present an alternating optimization approach for the joint design of transmit beamforming and RIS reflection. Our extensive simulation results on the SER performance of the proposed RIS-CBC-APSK framework corroborate our conducted performance analysis and showcase the superiority of both designed modulation schemes over the state-of-the-art RIS-CBC benchmarks.

The prompt-based learning paradigm, which bridges the gap between pre-training and finetuning, achieves state-of-the-art performance on several NLP tasks, particularly in few-shot settings.Despite being widely applied, promptbased learning is vulnerable to backdoor attacks.Textual backdoor attacks are designed to introduce targeted vulnerabilities into models by poisoning a subset of training samples through trigger injection and label modification.However, they suffer from flaws such as abnormal natural language expressions resulting from the trigger and incorrect labeling of poisoned samples.In this study, we propose ProAttack, a novel and efficient method for performing clean-label backdoor attacks based on the prompt, which uses the prompt itself as a trigger.Our method does not require external triggers and ensures correct labeling of poisoned samples, improving the stealthy nature of the backdoor attack.With extensive experiments on rich-resource and few-shot text classification tasks, we empirically validate ProAttack's competitive performance in textual backdoor attacks.Notably, in the rich-resource setting, ProAttack achieves state-of-the-art attack success rates in the clean-label backdoor attack benchmark without external triggers 1 .

In this paper, we employ a reconfigurable intelligent surface (RIS) to boost the single-carrier frequency-domain equalization (SC-FDE) transmission for both single- and multi-antenna broadband wireless communications. Different from the existing RIS-SC-FDE schemes that use an RIS to harvest cyclic delay diversity with a limited beamforming gain, our advanced schemes unlock the potential of the RIS in passive beamforming to maximize the receive signal-to-noise ratio. Concerning the high complexity issue, a low-complexity minorization-maximization (MM) method, which leads to a closed-form solution in each iteration, is developed for the RIS beamforming optimization problem. Finally, simulation results show that the proposed RIS-SC-FDE with the MM-based beamforming significantly outperforms the existing counterparts in terms of bit error rate.

Reconstructing an$s$-sparse signal${\boldsymbol{x}}$from an underdetermined noisy linear model arises in many applications. The iterative hard thresholding (IHT) and hard thresholding pursuit (HTP) algorithms are two popular sparse signal recovery algorithms. Since their recovery performances can be theoretically characterized by their sufficient conditions of stable sparse signal recovery, it is essential to establish less restrictive sufficient conditions. This work develops$\delta _{\text{2}s}$-based sufficient conditions for stable recovery with IHT and HTP. The two new sufficient conditions are significantly less restrictive than the state-of-the-art ones for IHT and HTP.

The Chinese radiology report summarization is a crucial component in smart healthcare that employs language models to summarize key findings in radiology reports and communicate these findings to physicians. However, most language models for radiology report summarization utilize a softmax transformation in their output layer, leading to dense alignments and strictly positive output probabilities. This density is inefficient, reducing model interpretability and giving probability mass to many unrealistic outputs. To tackle this issue, we propose a novel approach named nucleusmax. Nucleusmax is able to mitigate dense outputs and improve model interpretability by truncating the unreliable tail of the probability distribution. In addition, we incorporate nucleusmax with a copy mechanism, a useful technique to avoid professional errors in the generated diagnostic opinions. To further promote the research of radiology report summarization, we also have created a Chinese radiology report summarization dataset, which is freely available. Experimental results showed via both automatic and human evaluation that the proposed approach substantially improves the sparsity and overall quality of outputs over competitive softmax models, producing radiology summaries that approach the quality of those authored by physicians. In general, our work demonstrates the feasibility and prospect of the language model to the domain of radiology and smart healthcare.

As subclasses of spatially coupled turbo-like codes (SC-TCs), hybrid coupled serially concatenated codes (HC-SCCs) and spatially coupled serially concatenated codes (SC-SCCs) are attractive for streaming applications. However, it is a long-standing problem to estimate the error floors of HC-SCCs and SC-SCCs. To tackle this problem, we present a genie-aided approach in this paper. Specifically, we first show that the performance of a given HC-SCC or SC-SCC can be lower bounded by a hybrid concatenated code which is obtained by assuming the coupled sub-sequences are known or partially known. Second, we derive the average input-output weight enumerating functions (IOWEF) of the hybrid concatenated code ensembles corresponding to SC-SCC and HC-SCC. Third, the obtained IOWEFs are used to estimate the error floors. The numerical results show the tightness of the proposed method in estimating the error floors of SC-SCCs and HC-SCCs. We then use the proposed method to analyze the impact of the memories of the component convolutional codes on error floor. Particularly, we show that, for a given total memory order$v$, the lowest error floor is achieved by selecting the memories of the outer and inner component convolutional codes as$\lceil \frac {v}{2} \rceil $and$\lfloor \frac {v}{2} \rfloor $, respectively. In addition, for both SC-SCCs and HC-SCCs, reduced error floor can be achieved by increasing the outer coupling memory.

Based on the Threshold Predicate Encryption (TPE), the biometric authentication schemePassBioaims to correctly authenticate genuine end-users without leaking their biometric privacy information. However, this article proposes two impersonation attacks toPassBioby merely sending very few query messages. Specifically, an attacker is able to cheat the authentication server with probability 50% by sending the server a random query, or almost 100% by sending the server a collusion of old genuine queries, without being identified. Moreover, in order to defeat the impersonation attacks, this article presents a Verifiable Threshold Predicate Encryption (VTPE) scheme which includes three components: (1) a multi-segment TPE for reducing the computational cost and communication overhead significantly; (2) a segment-wise watermarking for defeating the random attacks; and (3) a challenge-response mechanism for defeating the replay and collusion attacks. In addition, the watermarking also creates a secure channel between the querying user and the server. The experiments on both simulated feature vectors and real face images demonstrate that the present attacks and countermeasures are effective and efficient.

Acquiring a sparse signal from an underdetermined linear system arises from numerous applications. Several hard thresholding algorithms have been developed for the sparse reconstruction. In particular, the so- called Newton-Step-based Iterative Hard Thresholding (NSIHT) and Newton-Step-based Hard Thresholding Pursuit (NSHTP) algorithms were developed by Menget al.recently. Although they are efficient, a faster sparse recovery algorithm with a better reconstruction performance is still needed. In this paper, we first propose a Pseudo-inverse-based Hard Thresholding sparse signal recovery algorithm called PHT for short. Unlike the Iterative Hard Thresholding (IHT) algorithm which uses the gradient of the objective function to iteratively update the solution, our proposed algorithm utilizes the pseudo-inverse of the sensing matrix to iteratively update the solution. We then analyze the computational complexity of PHT and show that it is$O(n^{2}/m^{2})$times faster than both NSIHT and NSHTP if they perform the same number of iterations, where$m$and$n$are the number of rows and columns of the sensing matrix$\boldsymbol {A}$. Furthermore, we establish a sufficient condition of stable recovery of the sparse signal with PHT by using the restricted isometry property (RIP) of the sensing matrix. Finally, extensive experiments are conducted which indicate that our proposed algorithm PHT is much faster than both NSIHT and NSHTP with overall better recovery performance.

The$\ell _{1}-\ell _{2}$-minimization is widely used to stably recover a$K$-sparse signal${\boldsymbol{x}}$from its low dimensional measurements${\boldsymbol{y}}=\boldsymbol{A}{\boldsymbol{x}}+\boldsymbol{v}$, where$\boldsymbol{A}$is a measurement matrix and$\boldsymbol{v}$is a noise vector. In this paper, we show that if the mutual coherence$\mu$of$\boldsymbol{A}$satisfies$\mu < \frac{4K-1- \sqrt{8K+1}}{\text{8}\;K^{2}-8\;K}$, then any$K$-sparse signal${\boldsymbol{x}}$can be stably recovered via the$\ell _{1}-\ell _{2}$-minimization. As far as we know, this is the best mutual coherence based sufficient condition of stably recovering$K$-sparse signals with the$\ell _{1}-\ell _{2}$-minimization.

Many applications operating in the Internet of Things (IoT) require timely and fair data collection from devices. This has motivated research into a new metric called Age of Information (AoI). This paper contributes to this effort by proposing to minimize the maximum average AoI (min-max AoI) in a multi-hop IoT network comprising of solar-powered Power Beacons (PBs). It outlines a Mixed Integer Linear Program (MILP) that jointly optimizes: (i) the beamforming vector used by PBs to charge devices, and (ii) routing, which determines how samples from devices are forwarded to a sink node, and (iii) the sampling time of sources. It also presents two protocols: Centralized Linear Relaxation (CLR) and Distributed Path Selection (DPS), respectively. CLR is run by the sink to determine the transmit power of PBs and the path of each source using two Linear Programs (LPs). On the other hand, DPS is a distributed approach whereby PBs and sources make their own decisions using local information. Our simulation results show that min-max AoI increases with the number of sources, but reduces with increasing number of PBs. The number of paths available to a source, the number of frames, and solar panel size have limited impact on performance. The min-max AoI of CLR and DPS is$1.60\times $and$1.95\times $higher than that of MILP.

This paper is concerned with detecting an integer parameter vector inside a box from a linear model that is corrupted with a noise vector following the Gaussian distribution. One of the commonly used detectors is the maximum likelihood detector, which is obtained by solving a box-constrained integer least squares problem, that is NP-hard. Two other popular detectors are the box-constrained rounding and Babai detectors due to their high efficiency of implementation. In this paper, we first present formulas for the success probabilities (the probabilities of correct detection) of these three detectors for two different situations: the integer parameter vector is deterministic and is uniformly distributed over the constraint box. Then, we give two simple examples to respectively show that the success probability of the box-constrained rounding detector can be larger than that of the box-constrained Babai detector and the latter can be larger than the success probability of the maximum likelihood detector when the parameter vector is deterministic, and prove that the success probability of the box-constrained rounding detector is always not larger than that of the box-constrained Babai detector when the parameter vector is uniformly distributed over the constraint box. Some relations between the results for the box constrained and ordinary cases are presented, and two bounds on the success probability of the maximum likelihood detector, which can easily be computed, are developed. Finally, simulation results are provided to illustrate our main theoretical findings.

Content-sharing is one of the major applications of vehicular networks. To fully utilize the spectrum and the connection time, rate-compatible codes are required when sharing content. In this paper, we present a simple and flexible method to construct low-complexity rate-compatible codes for content sharing. We first present a novel construction framework for rate-compatible codes via recursive block Markov superposition transmission (rBMST). In the proposed construction, the shared content is partitioned into equal-length data chunks and transmitted directly, while their replicas are taken as the inputs of a given number of parallel systematic encoders to generate parity-check chunks. These parity-check chunks are then transmitted in parallel in a recursive block Markov superposition transmission manner. The proposed construction is flexible in the sense that codes with arbitrary rates can be obtained by adjusting the number of parallel rBMST encoders and the number of randomly punctured bits. We show that the simplest construction, using repetition to generate the parity-check chunks, leads to high-performance and low-complexity rate-compatible rBMST (RC-rBMST) codes. Specifically, the extrinsic information transfer (EXIT) chart analysis shows that asymptotic thresholds of the repetition-based RC-rBMST (RB-RC-rBMST) codes are within 0.25 dB of the channel capacities for a wide range of coding rates. Numerical results are presented to confirm the advantages of the RB-RC-rBMST codes in performance and complexity. Particularly, the RB-RC-rBMST codes perform as well as BMST-R codes but with much lower computational complexities.

In this paper, we aim to give a unified performance limit analysis of the visible light-based positioning (VLP) for a vehicular user equipment (UE), which will help to understand the essence of time-domain localization cooperation and gain insights into how to improve the performance limit of the vehicular VLP system. This is challenging due to the complex system models and the complex dependency between UE location performance and orientation performance. To achieve the above goal, we will first characterize the closed-form error bounds of the UE location and orientation at each time slot, respectively, in terms of Fisher information. Generally, the VLP error will propagate over time as the vehicular UE moves, and hence the VLP error at the current time slot is affected by the VLP performance at the previous time slot, the UE mobility and the channel quality. Based on the obtained VLP error bounds, we then reveal the impact of prior UE location knowledge, UE mobility and signal-to-noise-ratio on the VLP performance. Furthermore, the time-domain evolution of the VLP error is studied, where the convergence of the time-domain VLP error evolution is established and its closed-form stable state is quantified, which will shed light on the long-term performance of the vehicular VLP system.

Generalized spatial modulation (GSM), which is a novel multiple-input multiple-output (MIMO) transmission technique, has attracted massive research attention in recent years. In this paper, we first utilize the orthogonal least squares (OLS) based detector for GSM detection. Then, we develop a sufficient condition of successful detection for the OLS based detector based on the restricted isometry property (RIP) of the channel matrix. Moreover, we prove that our sufficient condition is optimal. Finally, numerical simulations are conducted to illustrate that the proposed OLS based detector has better detection performance than the orthogonal matching pursuit (OMP) based detector with more or less the same time complexity.

Future Internet-of-Things (IoT) networks will consist of radio-frequency (RF) energy harvesting devices that are charged by solar-powered power beacons (PBs). To this end, this article aims to maximize the minimum data rate of devices acting as sources operating in a multihop IoT network. The main problem is to decide the amount of energy delivered by solar-powered PBs, routing of data from each source, and link scheduling, which determines the capacity of links. To this end, we make two contributions. First, we present a linear program (LP) to optimize the max-min rate of sources. Our LP considers nonlinear RF conversion at devices, energy storage loss at devices due to the imperfect battery, and time-varying channel quality, which affect the amount of energy harvested by devices. The second contribution is a novel distributed protocol called distributed max-min rate allocation (D-MRA), whereby devices only need local information, such as their battery and data buffer state to make decisions. Our results show that the max-min rate of D-MRA is 58.25% that of LP, which requires global information, in all tested cases.

Internet of Things and the related computing paradigms, such as cloud computing and fog computing, provide solutions for various applications and services with massive and high-dimensional data, while producing threats to the personal privacy. Differential privacy is a promising privacy-preserving definition for various applications and is enforced by injecting random noise into each query result such that the adversary with arbitrary background knowledge cannot infer sensitive input from the noisy results. Nevertheless, existing differentially private mechanisms have poor utility and high-computation complexity on high-dimensional data because the necessary noise in queries is proportional to the size of the data domain, which is exponential to the dimensionality. To address these issues, we develop a compressed sensing mechanism (CSM) that enforces differential privacy on the basis of the compressed sensing (CS) framework while providing accurate results to linear queries. We derive the utility guarantee of CSM theoretically. An extensive experimental evaluation on real-world data sets over multiple fields demonstrates that our proposed mechanism consistently outperforms several state-of-the-art mechanisms under differential privacy.

In 2014, a new security definition of a revocable identity-based signature (RIBS) with signing key exposure resistance was introduced. Based on this new definition, many scalable RIBS schemes with signing key exposure resistance were proposed. However, the security of these schemes is based on traditional complexity assumption, which is not secure against attacks in the quantum era. Lattice-based cryptography has many attractive features, and it is believed to be secure against quantum computing attacks. We reviewed existing lattice-based RIBS schemes and found that all these schemes are vulnerable to signing key exposure. Hence, in this paper, we propose the first lattice-based RIBS scheme with signing key exposure resistance by using the left-right lattices and delegation technology. In addition, we employ a complete subtree revocation method to ensure our construction meeting scalability. Finally, we prove that our RIBS scheme is selective-ID existentially unforgeable against chosen message attacks (EUF-sID-CMA) under the standard short integer solutions (SIS) assumption in the random oracle model.

Scheduling big data processing workflows involves both large-scale tasks and transmission of massive intermediate data among tasks, thus optimizing their completion time and monetary cost becomes a challenging issue. Besides, data streams are continuously generated, and dynamically submitted to clouds for real-time or near real-time processing. Naturally, responsive schedules are required to keep pace with such dynamic environments and this further aggravates the difficulty of the workflow scheduling problem. To address these issues, we first derive two theorems to minimize the completion time of a set of parallel workflow tasks and the start time of each workflow task, and then define the latest finish time for workflow tasks, which is also proved its advantage in reducing costs without delaying the completion of workflows. On the basis of these theorems, we propose a novel real-time scheduling algorithm using task-duplication, RTSATD, such that minimizing both the completion time and monetary cost of processing big data workflows in clouds. The performance of RTSATD is analyzed by using both synthesized and real-world workflows. The experimental results demonstrate the superiority of the proposed algorithm with respect to completion time (up to 28.73 percent) and resource utilization (up to 46.31 percent) over two existing approaches.

For industrial Internet of Things (IIoT), data trustworthiness should be maintained both at the time of sensing and at the time of transmission. This article is concerned with trustworthiness during transmission, which is determined by transmission reliability. We present a low-complexity and flexible method via partial and recursive superposition to improve the transmission reliability of IIoT, resulting in an IIoT with high trustworthiness. In our method, a portion of the previously transmitted data are superimposed onto the current transmitted data to introduce memory among different transmissions, which are then exploited by the windowed decoder to obtain performance gain. The proposed method is referred to as partially recursive block Markov superposition transmission of low-density parity-check (PrBMST-LDPC) codes. This article is focused on the construction of low-complexity PrBMST-LDPC codes since IIoT is resource-limited in nature. The first construction is the memory-one PrBMST-LDPC code. We present a simplified density evolution algorithm to optimize the superposition ratio for memory-one PrBMST-LDPC code. Both the analytical and numerical results show that PrBMST with memory one can be used to reduce the packet loss ratio (PLR) of IIoT using LDPC codes. Particularly, around 1.0 dB performance gain is obtained by PrBMST. We then present a low-complexity construction for PrBMST-LDPC codes with encoding memory larger than one. Simulation results show that compared with memory-one PrBMST, a further PLR reduction of around one order of magnitude can be obtained.

In current vector perturbation (VP) precoding architecture, the optimum perturbation vector is found with a closest lattice vector search for a given query point. In this work, we show that the query point should be judiciously chosen such that the effective noise power is minimized. The reduced noise power results in a better error rate performance for VP. The crux in the design is to decode an integer-multiple of lattice point within a modulo lattice architecture, where the integer- multiple can be a prime or a product of primes. Simulations show that around 2 dBs' performance gain can be observed even in the small-scale systems.

The orthogonal matching pursuit (OMP) algorithm is a commonly used algorithm for recovering K-sparse signals x ∈ ℝnfrom linear model y = Ax, where A ∈ ℝm×nis a sensing matrix. A fundamental question in the performance analysis of OMP is the characterization of the probability that it can exactly recover x for random matrix A. Although in many practical applications, in addition to the sparsity, x usually also has some additional property (for example, the nonzero entries of x independently and identically follow the Gaussian distribution), none of existing analysis uses these properties to answer the above question. In this paper, we first show that the prior distribution information of x can be used to provide an upper bound on ||x||21/||x||22, and then explore the bound to develop a better lower bound on the probability of exact recovery with OMP in K iterations. Simulation tests are presented to illustrate the superiority of the new bound.

The Korkine-Zolotareff (KZ) reduction is a widely used lattice reduction strategy in communications and cryptography. The Hermite constant, which is a vital constant of lattice, has many applications, such as bounding the length of the shortest nonzero lattice vector and orthogonality defect of lattices. The KZ constant can be used in quantifying some useful properties of KZ reduced matrices. In this paper, we first develop a linear upper bound on the Hermite constant and then use the bound to develop an upper bound on the KZ constant. These upper bounds are sharper than those obtained recently by the first two authors. Some examples on the applications of the improved upper bounds are also presented.

Nowadays, the serious security threat of industrial control system and sensors has become a major challenge with the rapid development of Industrial Internet of Things (IIoT). Man-in-the-middle (MITM) attack is a very common intrusion method, which will make a great security threat in the application of IIoT. In IIoT scenario, the lightweight safety certification can play a very important role in the development of data-intensive and decentralized applications running on billions of sensors and devices, preserving their security. Therefore, in this paper, a low-latency high-reliability security mechanism is proposed to avoid the MITM attack in IIoT scenario. First, combining the radio frequency fingerprint (RFF) technology with IIoT applications, a lightweight IIoT security architecture is proposed. Based on the proposed IIoT security architecture, the process of device access authentication and communication service is illustrated. Second, according to the requirement of IIoT identification method, an access authentication method of the device is proposed based on the RFF. The method of feature extraction, classifier designing, and the access authentication process is discussed in detail. Finally, the simulation results show that the identification rate of devices can reach 95% under SNR = 6 dB, and can nearly reach 100% under SNR = 15 dB. Through the new process of access authentication, the access authentication rate can reach 95% under SNR = 15 dB. Therefore, according to the simulation results, the new security mechanisms based on RFF can be used to avoid the MITM attack in IIoT scenario.

Compressed sensing is a signal processing technique, which can accurately recover sparse signals from linear measurements with far fewer number of measurements than those required by the classical Shannon-Nyquist theorem. Block sparse signals, i.e., the sparse signals whose nonzero coefficients occur in few blocks, arise from many fields. Block orthogonal matching pursuit (BOMP) is a popular greedy algorithm for recovering block sparse signals due to its high efficiency and effectiveness. By fully using the block sparsity of block sparse signals, BOMP can achieve very good recovery performance. This letter proposes a sufficient condition to ensure that BOMP can exactly recover the support of block K-sparse signals under the noisy case. This condition is better than existing ones.

The covariance-assisted matching pursuit (CAMP) algorithm has recently been proposed for recovering sparse signals f from noisy linear measurements based on a priori knowledge of the covariance and mean of the nonzero coefficients of f. It utilizes the a priori knowledge by incorporating the Gauss-Markov theorem into the orthogonal matching pursuit (OMP) algorithm and has a significantly better reconstruction performance than OMP. This letter develops sufficient conditions of exact support recovery of any k-sparse signals f via CAMP ink iterations, under the 12-bounded and Gaussian noises. These sufficient conditions are based on the restricted isometry constant of the sensing matrix and minimum magnitude of the nonzero elements of f, and are much better than the existing ones.

In many applications, including integer-forcing linear multiple-input and multiple-output (MIMO) receiver design, one needs to solve a successive minima problem (SMP) on an n-dimensional lattice to get an optimal integer coefficient matrix A* ∈ Zn×n. In this paper, we first propose an efficient optimal SMP algorithm with an O(n2) memory complexity. The main idea behind the new algorithm is it first initializes with a suitable suboptimal solution, which is then updated via a novel algorithm with only O(n2) flops in each updating, until A* is obtained. Different from existing algorithms which find A* column by column through using a sphere decoding search strategy n times, the new algorithm uses a search strategy once only. We then rigorously prove the optimality of the proposed algorithm. Furthermore, we theoretically analyze its complexity. In particular, we not only show that the new algorithm is Ω(n) times faster than the most efficient existing algorithm with polynomial memory complexity, but also assert that it is even more efficient than the most efficient existing algorithm with exponential memory complexity. Finally, numerical simulations are presented to illustrate the optimality and efficiency of our novel SMP algorithm.

Characterized by the ability to handle varying number of objects, tracking by detection framework becomes increasingly popular in multiobject tracking (MOT) problem. However, the tracking performance heavily depends on the object detector. Considering that data association optimization and association affinity model are two key parts in MOT, an online multipedestrian tracking method is proposed to formulate a more effective association affinity model. It includes a two-step data association taking advantage of rank-based dynamic motion affinity model. The rank-based dynamic motion affinity model is used to estimate the object state and refine the trajectory for each of target to achieve the noiseless trajectory. Both strategies are beneficial to eliminate ambiguous detection responses during association. To fairly verify the proposed method, three public datasets are adopted. Both qualitative and quantitative experiment results demonstrate the superiorities of the proposed tracking algorithm in comparison with its counterparts.

Frequency-modulated differential chaos shift keying ultrawideband (FM-DCSK UWB) system has attracted more and more attention in recent years because of its low-complexity and low-power advantages. Nevertheless, its system performance is severely degraded in the presence of narrowband interference (NBI), which further limits its practical applications. In this paper, an enhanced energy-based detector (EED) is proposed for the FM-DCSK UWB system to tackle this problem. Compared with the conventional energy detector (ED), the proposed EED significantly enhances the anti-NBI capability while maintaining the low-power and low-complexity feature. As a further insight, the analytical bit-error-rate (BER) expression of the proposed EED-based FM-DCSK UWB system is derived over additive white Gaussian noise as well as IEEE 802.15.4a multipath fading channels. Moreover, simulation results are carried out to demonstrate the accuracy of the theoretical analysis and the merit of the proposed EED. It is illustrated that the proposed EED achieves better performance than the conventional ED in various transmission scenarios. Thanks to the above-mentioned advantages, the proposed EED-based FM-DCSK UWB system appears to be an excellent candidate for low-power and low-complexity tactile Internet-of-Things applications, e.g., wireless sensor networks and wireless body area networks.

The lattice L(A) of a full-column rank matrix A ∈ Rm×nis defined as the set of all the integer linear combinations of the column vectors of A. The successive minima λi(A), 1 ≤ i ≤ n, of lattice L(A) are important quantities since they have close relationships with the following problems: shortest vector problem, shortest independent vector problem, and successive minima problem. These problems arise from many practical applications, such as communications and cryptography. This paper first investigates some properties of λi(A). Specifically, we develop lower and upper bounds on λi(A), where A are, respectively, the Cholesky factor of G1+ G2and (G1+ G2)-1for two given symmetric positive definitive matrices G1and G2. The bounds are, respectively, expressed as the successive minima of L(A1) and L(A2), and L(A1) and L(A2), where A1, A2, A1and A2are, respectively, the Cholesky factors of G1, G2, G1-1, and G2-1. Then, we show how some properties of λi(A) are used to design a suboptimal integer-forcing strategy for cloud radio access network. Our approach provides much higher time efficiency while keeping the same achievable rate as the algorithm reported by Bakoury and Nazer (I. E. Bakoury and B. Nazer, “Integer-forcing architectures for uplink cloud radio access networks,” in Proc. 55th Annu. Allerton Conf. Commun. Control Comput., Oct. 2007, pp. 67-75). Simulation tests are performed to illustrate our main results.

The Korkine-Zolotareff (KZ) reduction is one of the often used reduction strategies for lattice decoding. In this paper, we first investigate some important properties of KZ reduced matrices. Specifically, we present a linear upper bound on the Hermit constant which is around 7/8 times of the existing sharpest linear upper bound, and an upper bound on the KZ constant which is polynomially smaller than the existing sharpest one. We also propose upper bounds on the lengths of the columns of KZ reduced matrices, and an upper bound on the orthogonality defect of KZ reduced matrices which are even polynomially and exponentially smaller than those of boosted KZ reduced matrices, respectively. Then, we derive upper bounds on the magnitudes of the entries of any solution of a shortest vector problem (SVP) when its basis matrix is LLL reduced. These upper bounds are useful for analyzing the complexity and understanding numerical stability of the basis expansion in a KZ reduction algorithm. Finally, we propose a new KZ reduction algorithm by modifying the commonly used Schnorr-Euchner search strategy for solving SVPs and the basis expansion method proposed by Zhang et al. Simulation results show that the new KZ reduction algorithm is much faster and more numerically reliable than the KZ reduction algorithm proposed by Zhang et al., especially when the basis matrix is ill conditioned.

Functions with low differential uniformity have important applications in cryptography, coding theory, and sequence design. The differential spectrum of a cryptographic function is of great interest for estimating its resistance to some variants of differential cryptanalysis. Finding power permutations (i.e., monomial bijective mappings) over finite fields with low differential uniformity and determining their differential spectra have received a lot of attention over the past two decades. The objective of this paper is to study the differential properties of the well-known Kasami power permutations x p2k-pk+1 over GF(pn), where p is an odd prime and k is an integer with gcd(n, k) = 1. It turns out that this family of monomials is differentially (p + 1)-uniform. Our result in the case of p = 3 gives an affirmative solution to a recent conjecture by Xu, Cao, and Xu. Most notably, the differential spectrum of this family of power permutations is completely determined.

In this paper, we propose a novel successive two-way relaying (STWR) system that uses a pair of conventional half-duplex (HD) relays to mimic a full-duplex two-way relay (FD-TWR). Although classical FD-TWR is spectral efficient and expands cell coverage, the proposed STWR utilizes the existing HD infrastructure to boost the FD implementation and offers bi-directional data exchange and low-complexity residual self-interference (RSI) mitigation. To formulate STWR, we develop a unified signal model to facilitate the mitigation of the generalized self-interference (GSI). GSI consists of back-propagating interference due to two-way relaying, RSI of FD sources and inter-relay interference caused by the pairs of HD relays. Because the GSI channel matrix has a distinct row linearity, we propose an efficient digital approach to remove the GSI and design two low-complexity algorithms. These algorithms avoid RSI channel estimation, full-rank matrix, and complex matrix computation. Our analysis and simulations show that: 1) the proposed STWR achieves the multiplexing gain of the true FD-TWR; 2) the distance between the two HD relays should be optimized to achieve the highest spectral efficiency; and 3) the STWR system with two algorithms can achieve a diversity order of one or two, respectively. Therefore, the STWR concept achieves a flexible tradeoff between performance and complexity, potentially enabling large-scale relay deployments.

A lattice is a set of all the integer linear combinations of certain linearly independent vectors. One of the most important concepts on lattice is the successive minima which is of vital importance from both theoretical and practical applications points of view. In this paper, we first study some properties of successive minima and then employ some of them to improve the suboptimal algorithm for solving an optimization problem about maximizing the achievable rate of the integer-forcing strategy for cloud radio access networks in [1].

The null space property (NSP), which depends only on the null space of the column space of measurement matrix, has received much attention in compressed sensing. This letter considers NSP of the truncated l1-2minimization. It provides two versions of NSP of the truncated l1-2minimization, under which we present sufficient conditions for the truncated l1-2minimization to recover sparse and compressible signals. In addition, we discuss that the truncated l1-2stable NSP holds by Gaussian matrices of appropriate sizes with overwhelming probability.

Zero correlation zone (ZCZ) sequences are a class of spreading sequences having ideal auto-correlation and cross correlation in a zone around the origin. They have been extensively studied in recent years due to their important applications in quasi-synchronous code division multiple access systems. In this paper, a construction of ZCZ sequence sets is proposed based on perfect nonlinear functions. It generates multiple ZCZ sequence sets with the properties: 1) each sequence is perfect in the sense that its out-of-phase auto-correlation is always zero; 2) each ZCZ sequence set is optimal with respect to the Tang-Fan-Matsufuji bound in which all the sequences are pairwise cyclically distinct; and 3) the maximum inter-set cross correlation of multiple sequence sets achieves the well-known Sarwate bound.

We consider the detection of an integer vector x̂ ∈ ℤnfrom the linear observation y = Ax̂ + v, where A ∈ ℝm×nis a random matrix with independent and identically distributed (i.i.d.) standard Gaussian N (0, 1) entries, and ν ∈ ℝmis a noise vector with i.i.d. N (0, σ2) entries with given σ. In digital communications, x̂ is typically uniformly distributed over an n-dimensional box B. For this detection problem, successive interference cancellation decoders are popular due to their low complexity, and a detailed analysis of their word error rates (WERs) is highly useful. In this paper, we derive closed-form WER expressions for two cases: (1) x̂ ∈ℤnis fixed and (2) x̂ is uniformly distributed over B. We also investigate some of their properties in detail and show that they agree closely with simulated word error probabilities.

The integer-forcing (IF) linear multiple-input and multiple-output (MIMO) receiver is a recently proposed suboptimal receiver which nearly reaches the performance of the optimal maximum likelihood receiver for the entire signal-to-noise ratio (SNR) range and achieves the optimal diversity multiplexing tradeoff for the standard MIMO channel with no coding across transmit antennas in the high SNR regime. The optimal integer coefficient matrix A* ϵ ZNt×Ntfor IF maximizes the total achievable rate, where Nt is the column dimension of the channel matrix. To obtain A*, a successive minima problem (SMP) on an Nt-dimensional lattice that is suspected to be NP-hard needs to be solved. In this paper, an efficient exact algorithm for the SMP is proposed. For efficiency, our algorithm first uses the LLL reduction to reduce the SMP. Then, different from existing SMP algorithms which form the transformed A*column by column in Ntiterations, it first initializes with a suboptimal matrix which is the Nt× Ntidentity matrix with certain column permutations that guarantee this suboptimal matrix is a good initial solution of the reduced SMP. The suboptimal matrix is then updated, by utilizing the integer vectors obtained by employing an improved Schnorr-Euchner search algorithm to search the candidate integer vectors within a certain hyper-ellipsoid, via a novel and efficient algorithm until the transformed A*is obtained in only one iteration. Finally, the algorithm returns the matrix obtained by left multiplying the solution of the reduced SMP with the unimodular matrix that is generated by the LLL reduction. Simulation results show the optimality of our novel algorithm and indicates that the new one is much more efficient than existing optimal algorithms.

Wireless and digital communications applications require the detection of an integer vector x̂ from y = Ax̂ + v, where A ϵ ℝm×nis a random matrix whose entries are independent and identically distributed (i.i.d.) standard Gaussian N(0,1) entries, and v ϵ ℝmis a noise vector following the Gaussian distribution N(0,σ2) with given σ. The successive interference cancellation (SIC) decoders are frequently used to detect x̂ due to their high accuracy and low implementation complexity. However, to accurately characterize their performance, we need to analyze their symbol error rates (SER). In this paper, we derive a closed-form expression for the SER of the SIC decoders and investigate its properties. Simulated error probabilities of the SIC decoders agree closely with our theoretical expressions.

In communications, one frequently needs to detect a parameter vector x in a box from a linear model. The box-constrained rounding detector xBRand Babai detector xBBare often used to detect x due to their high probability of correct detection, which is referred to as success probability, and their high efficiency of implimentation. It is generally believed that the success probability PBRof xBRis not larger than the success probability PBBof xBB. In this paper, we first present formulas for PBRand PBBfor two different situations: x is deterministic and x is uniformly distributed over the constraint box. Then, we give a simple example to show that PBRmay be strictly larger than PBBif x is deterministic, while we rigorously show that pBR≤ pBBalways holds if x is uniformly distributed over the constraint box.

In many applications including communications, one may encounter a linear model where the parameter vector x̂ is an integer vector in a box. To estimate x̂, a typical method is to solve a box-constrained integer least squares problem. However, due to its high complexity, the box-constrained Babai integer point xBBis commonly used as a suboptimal solution. In this paper, we first derive formulas for the success probability PBBof xBBand the success probability POB of the ordinary Babai integer point xOBwhen x̂ is uniformly distributed over the constraint box. Some properties of PBBand POBand the relationship between them are studied. Then, we investigate the effects of some column permutation strategies on PBB. In addition to V-BLAST and SQRD, we also consider the permutation strategy involved in the LLL lattice reduction, to be referred to as LLL-P. On the one hand, we show that when the noise is relatively small, LLL-P always increases PBBand argue why both V-BLAST and SQRD often increase PBB; and on the other hand, we show that when the noise is relatively large, LLL-P always decreases PBBand argue why both V-BLAST and SQRD often decrease PBB. We also derive a column permutation invariant bound on PBB, which is an upper bound and a lower bound under these two opposite conditions, respectively. Numerical results demonstrate our findings. Finally, we consider a conjecture concerning xOBproposed by Ma et al. We first construct an example to show that the conjecture does not hold in general, and then show that it does hold under some conditions.

In this paper, we investigate joint antenna selection and spatial switching for quality-of-service-constrained energy efficiency (EE) optimization in a multiple-input multiple-output simultaneous wireless information and power transfer system. A practical linear power model taking into account the entire transmit-receive chain is accordingly utilized. The corresponding fractional-combinatorial and non-convex EE problem, involving joint optimization of eigenchannel assignment, power allocation, and active receive antenna set selection, subject to satisfying minimum sum-rate and power transfer constraints, is extremely difficult to solve directly. In order to tackle this, we separate the eigenchannel assignment and power allocation procedure with the antenna selection functionality. In particular, we first tackle the EE maximization problem under fixed receive antenna set using Dinkelbach-based convex programming, iterative joint eigenchannel assignment and power allocation, and low-complexity multi-objective optimization-based approach. On the other hand, the number of active receive antennas induces a tradeoff in the achievable sum-rate and power transfer versus the transmit-independent power consumption. We provide a fundamental study of the achievable EE with antenna selection and accordingly develop dynamic optimal exhaustive search and Frobenius-norm-based schemes. Simulation results confirm the theoretical findings and demonstrate that the proposed resource allocation algorithms can efficiently approach the optimal EE.

We modify the algorithm proposed by Sahraei et al. in 2015, resulting an algorithm with expected complexity of O(n log n) arithmetic operations to solve a special shortest vector problem arising in computer-and-forward design, where n is the dimension of the channel vector. This algorithm is more efficient than the best known algorithms with proved complexity.

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 the problem of finding the optimal coefficient vector that maximizes the computation rate at a relay in the compute-and-forward scheme. Based on the idea of sphere decoding, we propose a highly efficient algorithm that finds the optimal coefficient vector. First, we derive a novel algorithm to transform the original quadratic form optimization problem into a shortest vector problem (SVP) using the Cholesky factorization. Instead of computing the Cholesky factor explicitly, the proposed algorithm realizes the Cholesky factorization with only O(n) flops by taking advantage of the structure of the Gram matrix in the quadratic form. Then, we propose some conditions that can be checked with O(n) flops, under which a unit vector is the optimal coefficient vector. Finally, by considering some useful properties of the optimal coefficient vector, we modify the Schnorr-Euchner search algorithm to solve the SVP. We show that the estimated average complexity of our new algorithm is O(n1.5p0.5) flops for independent identically distributed (i.i.d.) Gaussian channel entries with SNR P based on the Gaussian heuristic. Simulations show that our algorithm is not only much more efficient than the existing ones that give the optimal solution, but also faster than some best known suboptimal methods. Besides, we show that our algorithm can be readily adapted to output a list of L best candidate vectors for use in the compute-and-forward design. The estimated average complexity of the resultant list-output algorithm is O(n2.5p0.5+ n1.5p0.5log(L) + nL) flops for i.i.d. Gaussian channel entries.

Overlapping community detection algorithm research is one of hot topics in current social network analysis. In this paper, we applied the idea of weighted label propagation to overlapping community detection algorithm design, and propose a weighted label propagation algorithm (WLPA). Moreover, in order to evaluate the performance results of various overlapping community detection algorithms, we put forward a series of evaluation criteria based on error distribution curve of overlapping vertices. The experiment results show that the algorithm has a faster speed and better community detection results, and the evaluation criteria is in line with the inherent characteristics of the social network overlapping community structure.

We consider the compute-and-forward protocol design problem with the objective being maximizing the computation rate at a single relay, and propose an efficient method that finds the optimal solution based on sphere decoding. The problem can be transformed into a shortest vector problem (SVP), which can be solved in two steps. First, by fully exploiting the specific structure of the associated Gram matrix using the hyperbolic transformation, the Cholesky factor can be computed with only n2/2 + O(n) flops. Then, taking into account of some useful properties of the optimal solution, we modify the Schnorr-Euchner search algorithm to solve the SVP. Numerical results show that our proposed branch-and-bound method is much more efficient than the existing one that gives the optimal solution. Besides, compared with the suboptimal methods, our method offers the best performance at a cost lower than that of the LLL based method and similar to that of the quadratic programming relaxation method.

The Korkine-Zolotareff (KZ) reduction has been used in communications and cryptography. In this paper, we modify a very recent KZ reduction algorithm proposed by Zhang et al., resulting in a new algorithm, which can be much faster and more numerically reliable, especially when the basis matrix is ill conditioned.

A common method to estimate an unknown integer parameter vector in a linear model is to solve an integer least squares (ILS) problem. A typical approach to solving an ILS problem is sphere decoding. To make a sphere decoder faster, the well-known LLL reduction is often used as preprocessing. The Babai point produced by the Babai nearest plane algorithm is a suboptimal solution of the ILS problem. First, we prove that the success probability of the Babai point as a lower bound on the success probability of the ILS estimator is sharper than the lower bound given by Hassibi and Boyd [1]. Then, we show rigorously that applying the LLL reduction algorithm will increase the success probability of the Babai point and give some theoretical and numerical test results. We give examples to show that unlike LLL's column permutation strategy, two often used column permutation strategies SQRD and V-BLAST may decrease the success probability of the Babai point. Finally, we show rigorously that applying the LLL reduction algorithm will also reduce the computational complexity of sphere decoders, which is measured approximately by the number of nodes in the search tree in the literature.