Search

Primality generation is the cornerstone of several essential cryptographic systems. The problem has been a subject of deep investigations, but there is still a substantial room for improvements. Typically, the algorithms used have two parts – trial divisions aimed at eliminating numbers with small prime factors and primality tests based on an easy-to-compute statement that is valid for primes and invalid for composites. In this paper, we will showcase a technique that will eliminate the first phase of the primality testing algorithms. The computational simulations show a reduction of the primality generation time by about 30 percent in the case of 1024-bit RSA key pairs. This can be particularly beneficial in the case of decentralized environments for shared RSA keys as the initial trial division part of the key generation algorithms can be avoided at no cost. This also significantly reduces the communication complexity. Another essential contribution of the paper is the introduction of a new one-way function that is computationally simpler than the existing ones used in public-key cryptography. This function can be used to create new random number generators, and it also could be potentially used for designing entirely new public-key encryption systems. [ABSTRACT FROM AUTHOR]

Variable-length (VL) coding with feedback is a commonly used technique that can approach point-to-point Shannon channel capacity with a significantly shorter average codeword length than fixed-length coding without feedback. This paper uses the inter-frame coding of Zeineddine and Mansour, originally introduced to address varying channel-state conditions in broadcast wireless communication, to approach capacity on point-to-point channels using VL codes without feedback. The per-symbol complexity is comparable to decoding the VL code with feedback (plus the additional complexity of a small peeling decoder amortized over many VL codes) and presents the opportunity for encoders and decoders that utilize massive parallel processing, where each VL decoder can process simultaneously. This paper provides an analytical framework and a design process for the degree distribution of the inter-frame code that allows the feedback-free system to achieve 96% or more of the throughput of the original VL code with feedback. As examples of VL codes, we consider non-binary (NB) low-density parity-check (LDPC), binary LDPC, and convolutional VL codes. The NB-LDPC VL code with an 8-bit CRC and an average codeword length of 336 bits achieves 85% of capacity with four rounds of ACK/NACK feedback. The proposed scheme using shared incremental redundancy without feedback achieves 97% of that performance or 83% of the channel capacity. [ABSTRACT FROM AUTHOR]

This paper is concerned with an important matrix condition in compressed sensing known as the restricted isometry property (RIP). We demonstrate that testing whether a matrix satisfies RIP is \ssr NP-hard. As a consequence of our result, it is impossible to efficiently test for RIP provided \ssr P\ne\ssr NP. [ABSTRACT FROM PUBLISHER]

Long period digital random sequence plays an important role in reliable communications and high security scenarios. This paper improved the method of generating long period digital random sequences based on the Residue Number System (RNS) and the Chinese Remainder Theorem (CRT), and a sequence mapping method after CRT extension. This paper proves that the period of sequence after mapping will not degenerate if the modulus used in the mapping stage is coprime with the period of the original sequence. By using the parallelism of RNS, the proposed method can generate sequences at high speed with fewer hardware resources. The NIST test results show that the pass rate of each test item is above 98.40%, which meets the NIST test confidence requirements, confirming the randomness of the generated sequences. An image encryption test is given as one of the example applications of the generated sequences. On the theoretical basis, by jointly optimizing the sequence mapping and iteration procedure, a hardware implementation architecture is also presented in this paper. The implementation is based on Xilinx XC7Z020CLG484-3 FPGA and compared with the implementations of classical chaotic maps. The results show that the proposed architecture has longer sequence period with less hardware resource consumption and higher generation speed and is more general. Meanwhile, the proposed architecture has fast phase switching ability, which is about 10 clock periods. This is one of the key attributes when the sequence is used in communication systems. [ABSTRACT FROM AUTHOR]

This paper compares the accuracy and complexity of Raghavan and Baum’s Reliability Output Viterbi Algorithm (ROVA), Polyanskiy’s accumulated information density (AID), and Fricke and Hoeher’s lower complexity approximation of ROVA. It turns out that AID is far less accurate than ROVA in practice. This paper proposes codeword information density (CID), which modifies AID to improve its accuracy and leads to a lower-complexity implementation of ROVA. The paper includes an analytical expression for the random variable describing the correct decoding probability computed by ROVA and uses this expression to characterize how the probabilities of correct decoding, undetected error, and negative acknowledgement behave as a function of the selected threshold for reliable decoding. This paper examines both the complexity and the simulation time of ROVA, CID, AID, and the Fricke and Hoeher approximation to ROVA. This paper also derives an expression for the union bound on the frame error rate for zero-terminated trellis codes with punctured symbols and uses it to optimize the order of symbol transmission in an incremental retransmission scheme. This paper concludes by comparing the performance of an incremental retransmission scheme using ROVA as a stopping condition to one that uses a CRC as a stopping condition. [ABSTRACT FROM AUTHOR]

We consider a variable-length source coding problem subject to local decodability constraints. In particular, we investigate the blocklength scaling behavior attainable by encodings of $r$ -sparse binary sequences, under the constraint that any source bit can be correctly decoded upon probing at most $d$ codeword bits. We consider both adaptive and non-adaptive access models, and derive upper and lower bounds that often coincide up to constant factors. Such a characterization for the fixed-blocklength analog of our problem, known as the bit probe complexity of static membership, remains unknown despite considerable attention from researchers over the last few decades. We also show that locally decodable schemes for sparse sequences are able to decode 0s (frequent source symbols) of the source with far fewer probes on average than they can decode 1s (infrequent source symbols), thus rigorizing the notion that infrequent symbols require high probe complexity, even on average. Connections to the fixed-blocklength model and to communication complexity are also briefly discussed. [ABSTRACT FROM AUTHOR]

This paper is concerned with a fuzzy analysis of power-flow (PF) involving uncertainties of load demands and network parameters. The crux of this paper is to propose an advanced fuzzy arithmetic. Fuzzy transformation method merges with backward–forward sweep in order to evaluate the contribution and propagation of uncertainty in IEEE 33-bus and 69-bus distribution systems. Results are validated by true intervals and random ranges. To determine true intervals, Global Optimization Problems (GOPs) are defined and solved through derivative-based and free techniques. To estimate random ranges, Monte-Carlo Simulations (MCSs) are employed. Our findings confirm that the sharpness of fuzzy intervals, tractability of computations, and applicability of possibility distributions. Following scenario-based evaluations, this paper discusses new implications of power losses, voltage profiles, optimal re-configuration, feeder extension, and reactive power compensation so that results would be beneficial to system planners and operators. Altogether, this paper provides a blueprint for a new way to handle uncertainties in a wide variety of power system problems without global optimization, linearization, and randomized simulations. [ABSTRACT FROM AUTHOR]

A list of papers to be published in future issues of "IEEE Transactions on Engineering Management" is presented including "Stochastic Entry of Competitors and Marketing Decisions," by Y.-S. Huang and J.-W. Ho "A Fuzzy Complexity Model for Enterprise Maintenance Projects," by K. Jenab and S. Shafiei-Monfared and "Optimal Feed-in Tariff Schedules," by G. Shrimali and E. Baker.

Information on the papers to be published in future issues of "IEEE Transactions on Engineering Management," including one on outsourcing and offshoring engineering projects, one on management software outsourcing and one on information technology.

Bi-Level Optimization (BLO) is originated from the area of economic game theory and then introduced into the optimization community. BLO is able to handle problems with a hierarchical structure, involving two levels of optimization tasks, where one task is nested inside the other. In machine learning and computer vision fields, despite the different motivations and mechanisms, a lot of complex problems, such as hyper-parameter optimization, multi-task and meta learning, neural architecture search, adversarial learning and deep reinforcement learning, actually all contain a series of closely related subproblms. In this paper, we first uniformly express these complex learning and vision problems from the perspective of BLO. Then we construct a best-response-based single-level reformulation and establish a unified algorithmic framework to understand and formulate mainstream gradient-based BLO methodologies, covering aspects ranging from fundamental automatic differentiation schemes to various accelerations, simplifications, extensions and their convergence and complexity properties. Last but not least, we discuss the potentials of our unified BLO framework for designing new algorithms and point out some promising directions for future research. A list of important papers discussed in this survey, corresponding codes, and additional resources on BLOs are publicly available at: https://github.com/vis-opt-group/BLO. [ABSTRACT FROM AUTHOR]

We consider practical schemes for binary dirty-paper channels and broadcast channels (BCs) with two receivers and varying channel quality. With the BC application in mind, this paper proposes a new design for binary dirty paper coding (DPC). By exploiting the concept of coset binning, the complexity of the system is greatly reduced when compared to the existing works. Some design challenges of the coset binning approach are identified and addressed. The proposed binary DPC system achieves similar performance to the state-of-the-art, superposition-coding-based system while demonstrating significant advantages in terms of complexity and flexibility of system design. For binary BCs, achieving the capacity generally requires the superposition of a normal channel code and a carefully designed channel code with non-uniform bit distribution. The non-uniform bit distribution is chosen according to the channel conditions. Therefore, to achieve the capacity for binary BCs with varying channel quality, it is necessary to use quantization codes of different rates, which significantly increases the implementation complexity. In this paper, we also propose a broadcast scheme that generalizes the concept of binary DPC, which we term soft DPC. By combining soft DPC with time sharing, we achieve a large percentage of the capacity for a wide range of channel quality with little complexity overhead. Our scheme uses only one fixed pair of codes for users 1 and 2, and a single quantization code, which possesses many practical advantages over traditional time sharing and superposition coding solutions and provides strictly better performance. [ABSTRACT FROM PUBLISHER]

This paper proposes an ordered sequence detection (OSD) for digital pulse interval modulation (DPIM) in optical wireless communications. Leveraging the sparsity of DPIM sequences, OSD shows a comparable performance to the optimal maximum likelihood sequence detection with much lower complexity. Compared with the widely adopted sample-by-sample optimal threshold detection (OTD), it considerably improves the bit-error-rate (BER) performance by mitigating error propagation. Moreover, this paper proposes a barrier signal-aided digital pulse interval modulation (BDPIM), where the last of every $K$ symbols is allocated with more power as an inserted barrier signal. BDPIM with OSD (BDPIM-OSD) can limit the error propagation between two adjacent barriers. To reduce the storing delay when using OSD to detect extremely large packets, we propose BDPIM with a combination of OTD and OSD (BDPIM-OTD-OSD), within which long sequences are cut into pieces and separately detected. Approximate upper bounds of the average BER performance of DPIM-OTD, DPIM-OSD, BDPIM-OSD, and BDPIM-OTD-OSD are analysed. Simulations are conducted to corroborate our analysis. Optimal parameter settings are also investigated in uncoded and coded systems by simulations. Simulation results show that the proposed OSD and BDPIM bring significant improvement in uncoded and coded systems over various channels. [ABSTRACT FROM AUTHOR]

List decoding of insertions and deletions in the Levenshtein metric is considered. The Levenshtein distance between two sequences is the minimum number of insertions and deletions needed to turn one of the sequences into the other. In this paper, a Johnson-like upper bound on the maximum list size when list decoding in the Levenshtein metric is derived. This bound depends only on the length and minimum Levenshtein distance of the code, the length of the received word, and the alphabet size. It shows that polynomial-time list decoding beyond half the Levenshtein distance is possible for many parameters. Further, we also prove a lower bound on list decoding of deletions with the well-known binary Varshamov–Tenengolts codes, which shows that the maximum list size grows exponentially with the number of deletions. Finally, an efficient list decoding algorithm for two insertions/deletions with VT codes is given. This decoder can be modified to a polynomial-time list decoder of any constant number of insertions/deletions. [ABSTRACT FROM AUTHOR]

The dawn of quantum computing brings on a revolution in the way combinatorially complex power system problems such as Unit Commitment are solved. The Unit Commitment problem complexity is expected to increase in the future because of the trend toward the increase of penetration of intermittent renewables. Even though quantum computing has proven effective for solving a host of problems, its applications for power systems’ problems have been rather limited. In this paper, a quantum unit commitment is innovatively formulated and the quantum version of the decomposition and coordination alternate direction method of multipliers (ADMM) is established. The above is achieved by devising quantum algorithms and by exploiting the superposition and entanglement of quantum bits (qubits) for solving subproblems, which are then coordinated through ADMM to obtain feasible solutions. The main contributions of this paper include: 1) the innovative development of a quantum model for Unit Commitment; 2) development of decomposition and coordination-supported framework which paves the way for the utilization of limited quantum resources to potentially solve the large-scale discrete optimization problems; 3) devising the novel quantum distributed unit commitment (QDUC) to solve the problem in a larger scale than currently available quantum computers are capable of solving. The QDUC results are compared with those from its classical counterpart, which validate the efficacy of quantum computing. [ABSTRACT FROM AUTHOR]

Digital supply chains (DSCs) can be useful in unlocking supply chains to gain competitive advantage as a driver of growth, while enabling rapid response, supporting novel technology-driven approaches, and creating innovative products and services. Partner selection (PS) is one of the crucial tasks in the successful digitalization of supply chain. However, the selection of a suitable partner is not an easygoing process and is mostly associated with complexity. Various criteria are considered during the partner evaluation process. This paper delivers an efficient evaluation process to assess alternative DSC partners. The proposed approach integrates the Pythagorean fuzzy sets (PFSs), analytic hierarchy process, and complex proportional assessment under a group decision making environment for the first time in the literature. PFSs can depict experts’ evaluations with a richer structure, allowing for a more representative decision making. A case study from Turkey is conducted to validate proposed approach. This study contributes to the existing literature by developing a new evaluation model to improve DSC PS process and by proposing a new hybrid PFSs-based framework. This paper can be useful to practitioners and researchers to better understand DSC PS problem and designing effective DSC partner evaluation systems. [ABSTRACT FROM AUTHOR]

There has been much recent interest in private information retrieval (PIR) in models where a database is stored across several servers using coding techniques from distributed storage, rather than being a simply replicated. In particular, a recent breakthrough result of Fazelli, Vardy, and Yaakobi introduces the notion of a PIR code and a PIR array code, and uses this notion to produce efficient PIR protocols. In this paper, we are interested in designing PIR array codes. We consider the case when we have $m$ servers, with each server storing a fraction $(1/s)$ of the bits of the database; here $s$ is a fixed rational number with $s > 1$. A PIR array code with the $k$ -PIR property enables a $k$ -server PIR protocol (with $k\leq m$) to be emulated on $m$ servers, with the overall storage requirements of the protocol being reduced. The communication complexity of a PIR protocol reduces as $k$ grows, so the virtual server rate, defined to be $k/m$ , is an important parameter. We study the maximum virtual server rate of a PIR array code with the $k$ -PIR property. We present upper bounds on the achievable virtual server rate, some constructions, and ideas how to obtain the PIR array codes with the highest possible virtual server rate. In particular, we present constructions that asymptotically meet our upper bounds and the exact largest virtual server rate is obtained when $1 < s \leq 2$. A $k$ -PIR code (and similarly a $k$ -PIR array code) is also a locally repairable code with symbol availability $k-1$. Such a code ensures $k$ parallel reads for each information symbol. So the virtual server rate is very closely related to the symbol availability of the code when used as a locally repairable code. The results of this paper are discussed also in this context where subspace codes also have an important role. [ABSTRACT FROM AUTHOR]

Reed-Solomon (RS) codes are widely used in distributed storage systems. In this paper, we study the repair bandwidth and sub-packetization size of RS codes. The repair bandwidth is defined as the amount of transmitted information from surviving nodes to a failed node. The RS code can be viewed as a polynomial over a finite field $GF(q^\ell)$ evaluated at a set of points, where $\ell $ is called the sub-packetization size. Smaller bandwidth reduces the network traffic in distributed storage, and smaller $\ell $ facilitates the implementation of RS codes with lower complexity. Recently, Guruswami and Wootters proposed a repair method for RS codes when the evaluation points are the entire finite field. While the sub-packetization size can be arbitrarily small, the repair bandwidth is higher than the minimum storage regenerating (MSR) bound. Tamo, Ye, and Barg achieved the MSR bound but the sub-packetization size grows faster than the exponential function of the number of the evaluation points. In this paper, we present code constructions and repair schemes that extend these results to accommodate different sizes of the evaluation points. In other words, we design schemes that provide points in between. These schemes provide a flexible tradeoff between the sub-packetization size and the repair bandwidth. In addition, we generalize our schemes to manage multiple failures. [ABSTRACT FROM AUTHOR]

With the rapid development of screen content video applications, screen content coding (SCC) is urgently needed to be used in commercial codecs. However, the extra encoding complexity introduced by the new SCC tools has posed a great challenge for its practical deployment. In this paper, motivated by our observations that there should be a fine-grained mapping between image content and candidate modes, we propose a two-step fast mode decision method to reduce the encoding complexity. First, we propose to use a convolution neural network (CNN) to automatically extract useful features for fine-grained content classification. Second, we build a precise and concise mapping from CUs to candidate modes by simultaneously considering CU content type, CU size, and mode complexity. Note that the spatial correlations between neighboring CUs and current CU are also utilized in candidate modes derivation. In addition to the two-step fast mode decision method, a content-aware early termination algorithm is further proposed to reduce the encoding complexity. Extensive experiments demonstrate that our method achieves better performance compared with state-of-the-art ones, with 50.13% total encoding complexity reduction and only 0.92% BD-rate increase. [ABSTRACT FROM AUTHOR]

In the paper, “semQA: SPARQL with Idempotent Disjunction” [4], the authors study the RDF query language SPARQL. In particular, they claim that some of the results presented in [1] are not correct. In this note, we refute the claims made in [4], and actually show that some of the formal results of [4] are incorrect. [ABSTRACT FROM PUBLISHER]

This paper provides upper and lower bounds on the optimal guessing moments of a random variable taking values on a finite set when side information may be available. These moments quantify the number of guesses required for correctly identifying the unknown object and, similarly to Arikan’s bounds, they are expressed in terms of the Arimoto-Rényi conditional entropy. Although Arikan’s bounds are asymptotically tight, the improvement of the bounds in this paper is significant in the non-asymptotic regime. Relationships between moments of the optimal guessing function and the MAP error probability are also established, characterizing the exact locus of their attainable values. The bounds on optimal guessing moments serve to improve non-asymptotic bounds on the cumulant generating function of the codeword lengths for fixed-to-variable optimal lossless source coding without prefix constraints. Non-asymptotic bounds on the reliability function of discrete memoryless sources are derived as well. Relying on these techniques, lower bounds on the cumulant generating function of the codeword lengths are derived, by means of the smooth Rényi entropy, for source codes that allow decoding errors. [ABSTRACT FROM PUBLISHER]

In this paper, we consider the problem of learning undirected graphical models from data generated according to the Glauber dynamics (also known as the Gibbs sampler). The Glauber dynamics is a Markov chain that sequentially updates individual nodes (variables) in a graphical model and it is frequently used to sample from the stationary distribution (to which it converges given sufficient time). Additionally, the Glauber dynamics is a natural dynamical model in a variety of settings. This paper deviates from the standard formulation of graphical model learning in the literature, where one assumes access to independent identically distributed samples from the distribution. Much of the research on graphical model learning has been directed toward finding algorithms with low computational cost. As the main result of this paper, we establish that the problem of reconstructing binary pairwise graphical models is computationally tractable when we observe the Glauber dynamics. Specifically, we show that a binary pairwise graphical model on p nodes with maximum degree d can be learned in time f(d)p^2\log p , for a function f(d) defined explicitly in this paper, using nearly the information-theoretic minimum number of samples. [ABSTRACT FROM AUTHOR]

Non-uniform constellation (NUC) is an advanced technology in digital terrestrial television broadcasting (DTTB) systems to reduce the shapping gap of BICM capacity to Shannon theoretical limit and provide performance gain. Two-dimensional NUC (2D-NUC) is a kind of NUC providing more gain but bringing higher demapping complexity at the receiver, which hinders its application prospects, especially in power limited systems. This paper proposes three novel demapping algorithms with reduced complexity for low to medium code rate 2D-NUCs in Advanced Television Systems Committee 3rd Generation (ATSC 3.0) standard. The proposed algorithms are based on the introduction of virtual points, the strategy of condensed symbols reduction and some reasonable approximations. There is a trade-off between the demapping complexity and performance. These three algorithms have different degrees of reduction in complexity and performance degradation, so they accommodate for different practical requirements. Theoretical analysis and simulation results are also given in this paper to prove the efficiency of the proposed demapping algorithms with reduced complexity. [ABSTRACT FROM AUTHOR]

Versatile Video Coding (VVC) was finalized in 2020 and offered promising coding efficiency with a bitrate reduction of about 50% for same video quality as High Efficiency Video Coding. However, its high encoding complexity is a heavy burden on real-time applications. In particular, the very high complexity in intra coding can be a big barrier into market entry. This paper presents an efficient low-complexity intra coding scheme, which employs downsampling and upsampling processes. The downsampling is simply performed by reducing the resolution of an original video in both horizontal and vertical directions. In the upsampling, convolutional neural network based super-resolution is used to increase the resolution of the reconstructed video. In addition, this paper thoroughly analyzes the performance and complexity of all intra coding tools in VVC. Experimental results demonstrate that the significantly high reduction of the encoding complexity can be achieved with acceptable video quality. [ABSTRACT FROM AUTHOR]

This paper investigates the optimal signal detection problem with a particular interest in large-scale multiple-input multiple-output (MIMO) systems. The problem is NP-hard and can be solved optimally by searching the shortest path on the decision tree. Unfortunately, the existing optimal search algorithms often involve prohibitively high complexities, which indicates that they are infeasible in large-scale MIMO systems. To address this issue, we propose a general heuristic search algorithm, namely, hyper-accelerated tree search (HATS) algorithm. The proposed algorithm employs a deep neural network (DNN) to estimate the optimal heuristic, and then use the estimated heuristic to speed up the underlying memory-bounded search algorithm. This idea is inspired by the fact that the underlying heuristic search algorithm reaches the optimal efficiency with the optimal heuristic function. Simulation results show that the proposed algorithm reaches almost the optimal bit error rate (BER) performance in large-scale systems, while the memory size can be bounded. In the meanwhile, it visits nearly the fewest tree nodes. This indicates that the proposed algorithm reaches almost the optimal efficiency in practical scenarios, and thereby it is applicable for large-scale systems. Besides, the code for this paper is available at https://github.com/skypitcher/hats. [ABSTRACT FROM AUTHOR]

Recommender systems are popular for personalization in online communities. Users, items, and other affiliated information such as tags, item genres, and user friends of an online community form a heterogenous information network. User profiling is the foundation of personalized recommender systems. It provides the basis to discover knowledge about an individual user’s interests to items. Typically, users are profiled with their direct explicit or implicit ratings, which ignored the inter-connections among users, items, and other entity nodes of the information network. This paper proposes a deep reinforcement user profiling approach for recommender systems. The user profiling process is framed as a sequential decision making problem which can be solved with a Reinforcement Learning (RL) agent. The RL agent interacts with the external heterogenous information network environment and learns a decision making policy network to decide whether there is an interest or preference path between a user and an unobserved item. To effectively train the RL agent, this paper proposes a multi-iteration training process to combine both expert and data-specific knowledge to profile users, generate meta-paths, and make recommendations. The effectiveness of the proposed approaches is demonstrated in experiments conducted on three datasets. [ABSTRACT FROM AUTHOR]

Low-density parity-check (LDPC) codes are widely used as error correction codes in new generation digital TV standards, such as the second generation of terrestrial digital video broadcasting standard (DVB-T2), Advanced Television Systems Committee (ATSC) 3.0, etc. The nonlinear belief propagation (BP) algorithm has excellent decoding performance for LDPC codes, but is often simplified in hardware implementations by linear min-sum (MS) algorithm due to its high complexity. This simplification also leads to over-estimation problems, which can be corrected by adding factors in conventional algorithms (e.g., normalized min-sum (NMS), offset min-sum (OMS), and variable scaling normalized min-sum (VMS) algorithms). However, the correction factors of these modified MS algorithms cannot adapt to different channels and modulations, and the performance needs further improvement. In this paper, the concepts of over-estimation value (OEV) and over-estimation rate (OER) are introduced to describe the over-estimation problem of the MS algorithm. Then, under the guidance of OEV and OER, a polygonal line min-sum (PMS) algorithm with correction factors adapted to different channels and modulations is proposed according to LLR distribution. Following the properties of OEV and OER, PMS algorithm is further simplified into Simplified PMS (SPMS) algorithm. LDPC codes from ATSC 3.0 are adopted in this paper to evaluate SPMS algorithm in comparison with the conventional algorithms. Extensive simulation results show that the SPMS algorithm for ATSC 3.0 LDPC decoder has at most 1.61dB, 0.24dB and 0.36dB gain over NMS, OMS and VMS algorithms respectively when frame error rate (FER) is at 10−4 level over additive white Gaussian noise (AWGN) channel with QPSK modulation. More importantly, the simulation results show that the SPMS algorithm can achieve much better performance than these modified MS algorithms over AWGN and Rayleigh channel with higher-order modulations or under limited maximum iteration number. [ABSTRACT FROM AUTHOR]

Optimal data detection of data transmitted over a linear channel can always be implemented through the Viterbi algorithm (VA). However, in many cases of interest the memory of the channel prohibits direct application of the VA. A popular and conceptually simple method in this case, studied since the early 1970s, is to first filter the received signal in order to shorten the memory of the channel, and then to apply a VA that operates with the shorter memory. We shall refer to this general concept as a channel shortening (CS) receiver. Although studied for almost four decades, an information theoretic understanding of what such a simple receiver solution is actually doing is not available. In this paper, we show that an optimized CS receiver has a direct correspondance to the chain rule of mutual information. Furthermore, we show that the tools for analyzing the ensuing achievable rates from an optimized CS receiver are precisely the same as those used for analyzing the achievable rates of a minimum mean-square-error (MMSE) receiver. [ABSTRACT FROM AUTHOR]

This paper discusses a method to regularize linear problems in presence of incomplete and noisy data generated by partially or totally unknown sources. The idea is to identify the “simplest” solution, looking for the system having the minimum number of degrees of freedom (NDF) compatible with the available data. It is shown that a normalized version of the trace norm (known as 1-Schatten norm in functional analysis) is a good convex approximation of the NDF of the field. This allows to use the trace norm as a convex surrogate of the NDF in the minimization process, taking advantage of the recent literature on rank minimization. Examples regarding MIMO beamforming from incomplete channel matrix, field interpolation with no a priori information on the sources, and land-mine identification using the total field are discussed. [ABSTRACT FROM PUBLISHER]

Learning a prototype from a set of given objects is a core problem in machine learning and pattern recognition. A commonly used approach for consensus learning is to formulate it as an optimization problem in terms of generalized median computation. Recently, a prototype-embedding approach has been proposed to transform the objects into a vector space, compute the geometric median, and then inversely transform back into the original space. This vector space embedding approach has been successfully applied in several domains, where the generalized median problem has inherent high-computational complexity (typically $\mathcal {NP}$ -hard) and thus approximate solutions are required. Generally, it can be expected that the embedding should be done in a distance-preserving manner. However, the previous work based on the prototype-embedding approach did not take this embedding aspect into account. In this paper, we discuss the drawbacks of the current prototype-embedding approach and present an extensive empirical study that provides strong evidence of significantly improved quality of generalized median computation using distance-preserving embedding (DPE) methods. We also give concrete suggestions about suitable DPE methods. Moreover, we show that this framework can be used to effectively compute other consensus objects like the closest string. Finally, a MATLAB toolbox resulting from this paper is made publically available in order to encourage other researchers to explore the embedding-based consensus computation. [ABSTRACT FROM AUTHOR]

This paper focuses on channel prediction techniques for massive multiple-input multiple-output (MIMO) systems. Previous channel predictors are based on theoretical channel models, which would be deviated from realistic channels. In this paper, we develop and compare a vector Kalman filter (VKF)-based channel predictor and a machine learning (ML)-based channel predictor using the realistic channels from the spatial channel model (SCM), which has been adopted in the 3GPP standard for years. First, we propose a low-complexity mobility estimator based on the spatial average using a large number of antennas in massive MIMO. The mobility estimate can be used to determine the complexity order of developed predictors. The VKF-based channel predictor developed in this paper exploits the autoregressive (AR) parameters estimated from the SCM channels based on the Yule-Walker equations. Then, the ML-based channel predictor using the linear minimum mean square error (LMMSE)-based noise pre-processed data is developed. Numerical results reveal that both channel predictors have substantial gain over the outdated channel in terms of the channel prediction accuracy and data rate. The ML-based predictor has larger overall computational complexity than the VKF-based predictor, but once trained, the operational complexity of ML-based predictor becomes smaller than that of VKF-based predictor. [ABSTRACT FROM AUTHOR]

Blind gain and phase calibration (BGPC) is a bilinear inverse problem involving the determination of unknown gains and phases of the sensing system, and the unknown signal, jointly. BGPC arises in numerous applications, e.g., blind albedo estimation in inverse rendering, synthetic aperture radar autofocus, and sensor array auto-calibration. In some cases, sparse structure in the unknown signal alleviates the ill-posedness of BGPC. Recently, there has been renewed interest in solutions to BGPC with careful analysis of error bounds. In this paper, we formulate BGPC as an eigenvalue/eigenvector problem and propose to solve it via power iteration, or in the sparsity or joint sparsity case, via truncated power iteration. Under certain assumptions, the unknown gains, phases, and the unknown signal can be recovered simultaneously. Numerical experiments show that power iteration algorithms work not only in the regime predicted by our main results, but also in regimes where theoretical analysis is limited. We also show that our power iteration algorithms for BGPC compare favorably with competing algorithms in adversarial conditions, e.g., with noisy measurement or with a bad initial estimate. [ABSTRACT FROM AUTHOR]

Encoding multiple videos in parallel and transmitting them as one joint stream over a limited bandwidth have become a popular strategy for broadcasting, which brings an opportunity to allocate different bitrate for each sequence to meet different demands. In this paper, considering visual experience for human beings, we propose a joint rate allocation scheme aims to reach an equal visual quality among all sequences by minimizing the distortion variance of all the sequences (denoted as minVAR problems). Existing methods assigned bits directly in proportion to their complexity measures and we named them as complexity based allocation scheme (CAS) methods. CAS methods rely on the accuracy of the complexity measures which can hardly be improved under limited computing resources. Also complexities may not be directly related to the distortions. To address these problems, we present a novel joint rate-distortion (R-D) based allocation scheme (RDAS) in this paper. Our proposed scheme can fit for different R-D models and in our method we model the R-D relationship with a hyperbolic function (RDAS-H). We also derive a closed-form solution of RDAS-H by a proposed joint R-D relationship. We integrated the RDAS-H method in high efficiency video coding reference software HM16.0. Experimental results demonstrate that our RDAS-H saves 75.29% variance on average over the related CAS-based method, where we apply both low delay and random access configurations with four different overall bandwidths for all classes recommended by the Joint Collaborative Team on Video Coding. Besides, RDAS-H also saves 36.62% variance on average over our previous method. The proposed RDAS-H method improves the performance significantly while requiring negligible computational cost. [ABSTRACT FROM AUTHOR]

In this paper, we consider a simple coding scheme for spatial modulation, where the same set of active transmit antennas is repeatedly used over consecutive multiple transmissions. Based on a Gaussian approximation, an approximate maximum likelihood (ML) detection problem is formulated to detect the indices of active transmit antennas. We show that the solution to the approximate ML detection problem can achieve a full coding gain. Furthermore, we develop a low-complexity iterative algorithm to solve the problem with low complexity based on a well-known machine learning approach, i.e., variational inference. Simulation results show that the proposed algorithm can have a near ML performance. A salient feature of the proposed algorithm is that its complexity is independent of the number of active transmit antennas, whereas an exhaustive search for the ML problem requires a complexity that grows exponentially with the number of active transmit antennas. [ABSTRACT FROM AUTHOR]

This paper introduces the simultaneous partial-inverse problem (SPI) for polynomials and develops its application to decoding interleaved Reed–Solomon codes beyond half the minimum distance. While closely related both to standard key equations and to well-known Padé approximation problems, the SPI problem stands out in several respects. First, the SPI problem has a unique solution (up to a scale factor), which satisfies a natural degree bound. Second, the SPI problem can be transformed (monomialized) into an equivalent SPI problem where all moduli are monomials. Third, the SPI problem can be solved by an efficient algorithm of the Berlekamp–Massey type. Fourth, decoding interleaved Reed–Solomon codes (or subfield-evaluation codes) beyond half the minimum distance can be analyzed in terms of a partial-inverse condition for the error pattern: if that condition is satisfied, then the (true) error locator polynomial is the unique solution of a standard key equation and can be computed in many different ways, including the well-known multi-sequence Berlekamp–Massey algorithm and the SPI algorithm of this paper. Two of the best performance bounds from the literature (the Schmidt–Sidorenko–Bossert bound and the Roth–Vontobel bound) are generalized to hold for the partial-inverse condition and thus to apply to several different decoding algorithms. [ABSTRACT FROM AUTHOR]

This paper investigates the design and analysis of minimum mean square error (MMSE) turbo decision feedback equalization (DFE), with expectation propagation (EP), for single carrier modulations. Classical non iterative DFE structures have substantial advantages at high-data rates, even compared with turbo linear equalizers-interference cancellers (LE-IC), hence making turbo DFE-IC schemes an attractive solution. In this paper, we derive an iterative DFE-IC, capitalizing on the use of soft feedback based on expectation propagation, along with the use of prior information for improved filtering and interference cancellation. This turbo iterative DFE-IC significantly outperforms turbo LE-IC, especially at high-spectral efficiency and also exhibits performance improvements over existing DFE-IC variants. The proposed scheme can also be self-iterated, as done in the recent trend on EP-based equalizers, and it is shown to be an attractive alternative to linear self-iterated receivers. For time-varying (TV) filter equalizers, an efficient matrix inversion scheme is also proposed, considerably reducing the computational complexity relative to existing methods. Using finite-length and asymptotic analysis on a severely selective channel, the proposed DFE-IC is shown to achieve higher rates than known alternatives, with better waterfall thresholds and faster convergence, while keeping a similar computational complexity. [ABSTRACT FROM AUTHOR]

This paper considers the problem of user association to small-cell base stations (SBSs) in a heterogeneous and small-cell network (HetSNet). Two optimization problems are investigated, namely, maximizing the set of associated users to the SBSs (the unweighted problem) and maximizing the set of weighted associated users to the SBSs (the weighted problem), under signal-to-interference-plus-noise ratio constraints. Both problems are formulated as linear integer programs. The weighted problem is known to be NP-hard, and in this paper, the unweighted problem is proved to be NP-hard as well. Therefore, this paper develops two heuristic polynomial-time algorithms to solve both problems. The computational complexity of the proposed algorithms is evaluated and is shown to be far more efficient than the complexity of the optimal brute-force (BF) algorithm. Moreover, this paper benchmarks the performance of the proposed algorithms against the BF algorithm, the branch-and-bound CPLEX-based algorithm, and state-of-the-art algorithms, through numerical simulations. The results demonstrate the close-to-optimal performance of the proposed algorithms. They also show that the weighted problem can be solved to provide solutions that are fair between users or to balance the load among SBSs. [ABSTRACT FROM PUBLISHER]

A two-user Gaussian broadcast channel (GBC) with finite input constellations is addressed in this paper. The constellation-constrained capacity region for the two-user GBC by recently proposed bit-division multiplexing (BDM) is derived. BDM can be seen as a practical implementation of constellation-constrained nonlinear superposition coding (SC). For comparison, the constellation-constrained capacity region for the two-user GBC by traditional constellation-constrained linear SC is also computed. With similar implementation complexity, BDM outperforms traditional constellation-constrained linear SC with lower shaping loss in the capacity defined in this paper. Analytical results show that the upper boundary of the capacity region for the two-user GBC can be well approached by BDM with amplitude phase-shift keying modulation, which could be considered as the preliminary demonstration on the applicability of BDM in practical systems. [ABSTRACT FROM PUBLISHER]

This paper presents a two-stage approach to handle fixed-outline floorplanning for mixed size modules, named F-FM. F-FM combines the advantages of the analytical approach and the slicing tree representation. Thus, it is not only suitable for handling fixed-outline floorplanning but also can be extended to handle other important issues in floorplanning such as routability or thermal effect in addition to wirelength. Recently, low power has become big challenges in very large-scale integration designs, which makes voltage-island driven floorplanning more important than ever. Although the problem has been discussed by previous works, no paper considers signal wirelength, powerplanning, and voltage drop at the same time under the fixed-outline constraint. Thus, this paper extends F-FM to handle this problem and consider these issues by properly dividing modules in a voltage domain into several islands. The experimental results show our approach obtains the best results in these problems. [ABSTRACT FROM AUTHOR]

Approximate message passing (AMP) is a low-cost iterative parameter-estimation technique for certain high-dimensional linear systems with non-Gaussian distributions. AMP only applies to independent identically distributed (IID) transform matrices, but may become unreliable (e.g., perform poorly or even diverge) for other matrix ensembles, especially for ill-conditioned ones. To solve this issue, orthogonal/vector AMP (OAMP/VAMP) was proposed for general right-unitarily-invariant matrices. However, the Bayes-optimal OAMP/VAMP (BO-OAMP/VAMP) requires a high-complexity linear minimum mean square error (MMSE) estimator. This prevents OAMP/VAMP from being used in large-scale systems. To address the drawbacks of AMP and BO-OAMP/VAMP, this paper offers a memory AMP (MAMP) framework based on the orthogonality principle, which ensures that estimation errors in MAMP are asymptotically IID Gaussian. To realize the required orthogonality for MAMP, we provide an orthogonalization procedure for the local memory estimators. In addition, we propose a Bayes-optimal MAMP (BO-MAMP), in which a long-memory matched filter is used for interference suppression. The complexity of BO-MAMP is comparable to AMP. To asymptotically characterize the performance of BO-MAMP, a state evolution is derived. The relaxation parameters and damping vector in BO-MAMP are optimized based on state evolution. Most crucially, the state evolution of the optimized BO-MAMP converges to the same fixed point as that of the high-complexity BO-OAMP/VAMP for all right-unitarily-invariant matrices, and achieves the Bayes optimal MSE predicted by the replica method if its state evolution has a unique fixed point. Finally, simulations are provided to verify the theoretical results’ validity and accuracy. [ABSTRACT FROM AUTHOR]

In the classical model for (information theoretically secure) Private Information Retrieval (PIR) due to Chor, Goldreich, Kushilevitz and Sudan, a user wishes to retrieve one bit of a database that is stored on a set of ${n}$ servers, in such a way that no individual server gains information about which bit the user is interested in. The aim is to design schemes that minimise the total communication between the user and the servers. More recently, there have been moves to consider more realistic models where the total storage of the set of servers, or the per server storage, should be minimised (possibly using techniques from distributed storage), and where the database is divided into ${R}$ -bit records with ${R}>1$ , and the user wishes to retrieve one record rather than one bit. When ${R}$ is large, downloads from the servers to the user dominate the communication complexity and so the aim is to minimise the total number of downloaded bits. Work of Shah, Rashmi and Ramchandran shows that at least ${R}+1$ bits must be downloaded from servers in the worst case, and provides PIR schemes meeting this bound. Sun and Jafar have considered the download cost of a scheme, defined as the ratio of the message length ${R}$ and the total number of bits downloaded. They determine the best asymptotic download cost of a PIR scheme (as ${R}\rightarrow \infty $) when a database of ${k}$ messages is stored by ${n}$ servers. This paper provides various bounds on the download complexity of a PIR scheme, generalising those of Shah et al. to the case when the number ${n}$ of servers is bounded, and providing links with classical techniques due to Chor et al. The paper also provides a range of constructions for PIR schemes that are either simpler or perform better than previously known schemes. These constructions include explicit schemes that achieve the best asymptotic download complexity of Sun and Jafar with significantly lower upload complexity, and general techniques for constructing a scheme with good worst case download complexity from a scheme with good download complexity on average. [ABSTRACT FROM AUTHOR]

Recently chaos theory has emerged as a powerful tool to address forecasting problems of nonlinear time series, since it is able to meet the dynamical and geometrical structures of very complex systems, reaching higher accuracy on the prediction values than the classical approaches. This paper aims at applying the chaos theory principles to different problems, in order to pursue high levels of accuracy on the predicted results. After the verification of the chaotic behavior of the datasets taken into analysis through the largest Lyapunov exponent research, the detection of the suitable embedding dimension and time delay has been carried out, in order to reconstruct the phase space of the underlying dynamical systems. Three different predictive methods have been proposed for different datasets. Finally, the performance comparison with the moving average model, a deep neural network based strategy, and a chaos theory based algorithm recently proposed in literature has been provided. [ABSTRACT FROM AUTHOR]

AV1 is an open-source video coding technique developed by Alliance for Open Media (AOMedia). Many powerful coding tools introduced to AV1 has made its encoding time significantly increased. In this paper, we aim at simplifying the AV1 encoder by facilitating selection of some coding tools depending on users’ specific application preference. We firstly design a coding tool OFF-test to evaluate coding performance of intra, inter, and in-loop filter coding tools in AV1 encoder in order to define a criterion to evaluate the importance of each coding tool by measuring the Bjøntegaard delta bit rate (BDBR) loss and time saving (TS) when each coding tool is turned OFF. Furthermore, the importance of each coding tool is analyzed based on the predefined criterion. Lastly, we suggest two intra coding tool selection methods, three inter coding tool selection methods, and three overall coding tool selection methods to simplify AV1 encoder based on users’ preference of quality-priority or low-complexity-priority. Experimental results show that our proposed low-complexity-priority selection method saves 30.72% of encoding time with only 0.91% loss in BDBR sense, and the quality-priority selection method saves 4.64% of encoding time with 0.02% BDBR loss. [ABSTRACT FROM AUTHOR]

In this paper, we study a simplified affine motion model-based coding framework to overcome the limitation of a translational motion model and maintain low-computational complexity. The proposed framework mainly has three key contributions. First, we propose to reduce the number of affine motion parameters from 6 to 4. The proposed four-parameter affine motion model can not only handle most of the complex motions in natural videos, but also save the bits for two parameters. Second, to efficiently encode the affine motion parameters, we propose two motion prediction modes, i.e., an advanced affine motion vector prediction scheme combined with a gradient-based fast affine motion estimation algorithm and an affine model merge scheme, where the latter attempts to reuse the affine motion parameters (instead of the motion vectors) of neighboring blocks. Third, we propose two fast affine motion compensation algorithms. One is the one-step sub-pixel interpolation that reduces the computations of each interpolation. The other is the interpolation-precision-based adaptive block size motion compensation that performs motion compensation at the block level rather than the pixel level to reduce the number of interpolation. Our proposed techniques have been implemented based on the state-of-the-art high-efficiency video coding standard, and the experimental results show that the proposed techniques altogether achieve, on average, 11.1% and 19.3% bits saving for random access and low-delay configurations, respectively, on typical video sequences that have rich rotation or zooming motions. Meanwhile, the computational complexity increases of both the encoder and the decoder are within an acceptable range. [ABSTRACT FROM AUTHOR]

Collaboration is complex. To solve a problem occurring in collaboration, using computers, we must first define and specify the problem. This paper presents a challenging problem in collaboration, called group role assignment with cooperation and conflict factors (GRACCFs). This problem’s solution aims at creating a high-performance group by role assignment with consideration of cooperation and conflicts between agents. The contribution of this paper is the formalization of the proposed problem, a confirmation of the complexity of the problem, a practical solution that uses the IBM ILOG CPLEX optimization package (ILOG), a verification of the benefits of solving the GRACCF problem by simulations and a practical way of collecting the required factors to support decision makers in solving such a problem within a real-world scenario. Experiments are used to verify the efficiency of the proposed ILOG solution. [ABSTRACT FROM AUTHOR]