By exploiting the inherent sparsity of wireless channels, the channel estimation in an orthogonal frequency division multiplexing (OFDM) system can be cast as a compressed sensing (CS) problem to estimate the channel more accurately. Practically, matching pursuit algorithms such as orthogonal matching pursuit (OMP) are used, where path delays of the channel is guessed based on correlation values for every quantized delay with residual. This full search approach requires a predefined grid of delays with high resolution, which induces the high computational complexity because correlation values with residual at a huge number of grid points should be calculated. Meanwhile, the correlation values with high resolution can be obtained by interpolation between the correlation values at a low resolution grid. Also, the interpolation can be implemented with a low pass filter (LPF). By using this fact, in this paper we substantially reduce the computational complexity to calculate the correlation values in channel estimation using CS.
Xu BAO Wence ZHANG Jisheng DAI Jianxin DAI
In this paper, we devise low-complexity uplink detection algorithms for Massive MIMO systems. We treat the uplink detection as an ill-posed problem and adopt the Landweber Method to solve it. In order to reduce the computational complexity and increase the convergence rate, we propose improved Landweber Method with optimal relax factor (ILM-O) algorithm. In addition, to reduce the order of Landweber Method by introducing a set of coefficients, we propose reduced order Landweber Method (ROLM) algorithm. An analysis on the convergence and the complexity is provided. Numerical results demonstrate that the proposed algorithms outperform the existing algorithm.
In many communications applications, maximum-likelihood decoding reduces to solving an integer least-squares problem, which is NP-hard in the worst case. It has recently been shown that over a wide range of dimensions and SNRs, the branch and bound (BB) algorithm can be used to find the exact solution with an expected complexity that is roughly cubic in the dimension of the problem. However, the computational complexity becomes prohibitive if the SNR is too low and/or the dimension of the problem is too large. The dichotomous coordinate descent (DCD) algorithm provides low complexity, but its detection performance is not as good as that of the BB detector. Two methods are developed to bound the optimal detector cost to reduce the complexity of BB in this paper. These methods are DCD-based detectors for MIMO and multiuser detection in the scenario of a large number of transmitting antennas/users. First, a combined detection technique based on the BB and DCD algorithms is proposed. The technique maintains the advantages of both algorithms and achieves a good trade-off between performance and complexity compared to using only the BB or DCD algorithm. Second, since the first feasible solution obtained from the BB search is the solution of the decorrelating decision feedback (DF) method and because DCD results in better accuracy than the decorrelating DF solution, we propose that the first feasible solution of the BB algorithm be obtained by the box-constrained DCD algorithm rather than the decorrelating DF detector. This method improves the precision of the initial solution and identifies more branches that can be eliminated from the search tree. The results show that the DCD-based BB detector provides optimal detection with reduced worst-case complexity compared to that of the decorrelating DF-based BB detector.
Hiroki MANIWA Takayuki OKI Akira SUZUKI Kei UCHIZAWA Xiao ZHOU
The energy of a threshold circuit C is defined to be the maximum number of gates outputting ones for an input assignment, where the maximum is taken over all the input assignments. In this paper, we study computational power of threshold circuits of energy at most two. We present several results showing that the computational power of threshold circuits of energy one and the counterpart of energy two are remarkably different. In particular, we give an explicit function which requires an exponential size for threshold circuits of energy one, but is computable by a threshold circuit of size just two and energy two. We also consider MOD functions and Generalized Inner Product functions, and show that these functions also require exponential size for threshold circuits of energy one, but are computable by threshold circuits of substantially less size and energy two.
We consider a device-to-device (D2D) underlaid cellular network where D2D communications are allowed to share the same radio spectrum with cellular uplink communications for improving spectral efficiency. However, to protect the cellular uplink communications, the interference level received at a base station (BS) from the D2D communications needs to be carefully maintained below a certain threshold, and thus the BS coordinates the transmit power of the D2D links. In this paper, we investigate on-off power control for the D2D links, which is known as a simple but effective technique due to its low signaling overhead. We first investigate the optimal on-off power control algorithm to maximize the sum-rate of the D2D links, while satisfying the interference constraint imposed by the BS. The computational complexity of the optimal algorithm drastically increases with D2D link number. Thus, we also propose an on-off power control algorithm to significantly reduce the computational complexity, compared to the optimal on-off power control algorithm. Extensive simulations validate that the proposed algorithm significantly reduces the computational complexity with a marginal sum-rate offset from the optimal algorithm.
As the capabilities and costs of Artificial Intelligence (AI) and of sensors (IoT) continue to improve, the concept of a “control system” can evolve beyond the operation of a discrete technical system based on numerical information and enter the realm of large-scale systems with both technical and social characteristics based on both numerical and unstructured information. This evolution has particular significance for applying the principles of Autonomous Decentralised Systems (ADS) [1]. This article considers the possible roles for ADS in complex technical and social systems extending up to global scales.
Zhihua NIU Deyu KONG Yanli REN Xiaoni DU
The k-error linear complexity of a sequence is a fundamental concept for assessing the stability of the linear complexity. After computing the k-error linear complexity of a sequence, those bits that cause the linear complexity reduced also need to be determined. For binary sequences with period 2pn, where p is an odd prime and 2 is a primitive root modulo p2, we present an algorithm which computes the minimum number k such that the k-error linear complexity is not greater than a given constant c. The corresponding error sequence is also obtained.
Ken-ichiro MORIDOMI Kohei HATANO Eiji TAKIMOTO
We prove generalization error bounds of classes of low-rank matrices with some norm constraints for collaborative filtering tasks. Our bounds are tighter, compared to known bounds using rank or the related quantity only, by taking the additional L1 and L∞ constraints into account. Also, we show that our bounds on the Rademacher complexity of the classes are optimal.
Kai WANG Jiaying DING Yili XIA Xu LIU Jinguang HAO Wenjiang PEI
Computing autocorrelation coefficient can effectively reduce the influence of additive white noise, thus estimation precision will be improved. In this paper, an autocorrelation-like function, different from the ordinary one, is defined, and is proven to own better linear predictive performance. Two algorithms for signal model are developed to achieve frequency estimates. We analyze the theoretical properties of the algorithms in the additive white Gaussian noise. The simulation results match with the theoretical values well in the sense of mean square error. The proposed algorithms compare with existing estimators, are closer to the Cramer-Rao bound (CRLB). In addition, computer simulations demonstrate that the proposed algorithms provide high accuracy and good anti-noise capability.
Muhammad Syafiq BIN AB MALEK Mohd Anuaruddin BIN AHMADON Shingo YAMAGUCHI
Response property is a kind of liveness property. Response property problem is defined as follows: Given two activities α and β, whenever α is executed, is β always executed after that? In this paper, we tackled the problem in terms of Workflow Petri nets (WF-nets for short). Our results are (i) the response property problem for acyclic WF-nets is decidable, (ii) the problem is intractable for acyclic asymmetric choice (AC) WF-nets, and (iii) the problem for acyclic bridge-less well-structured WF-nets is solvable in polynomial time. We illustrated the usefulness of the procedure with an application example.
Motoko TACHIBANA Kohei YAMAMOTO Kurato MAENO
Radar is expected in advanced driver-assistance systems for environmentally robust measurements. In this paper, we propose a novel radar signal segmentation method by using a complex-valued fully convolutional network (CvFCN) that comprises complex-valued layers, real-valued layers, and a bidirectional conversion layer between them. We also propose an efficient automatic annotation system for dataset generation. We apply the CvFCN to two-dimensional (2D) complex-valued radar signal maps (r-maps) that comprise angle and distance axes. An r-maps is a 2D complex-valued matrix that is generated from raw radar signals by 2D Fourier transformation. We annotate the r-maps automatically using LiDAR measurements. In our experiment, we semantically segment r-map signals into pedestrian and background regions, achieving accuracy of 99.7% for the background and 96.2% for pedestrians.
Chang-Hee KANG Sung-Soon PARK Young-Hwan YOU Hyoung-Kyu SONG
In wireless communication systems, OFDM technology is a communication method that can yield high data rates. However, OFDM systems suffer high PAPR values due to the use of many of subcarriers. The SLM and the PTS technique were proposed to solve the PAPR problem in OFDM systems. However, these approaches have the disadvantage of having high complexity. This paper proposes a method which has lower complexity than the conventional PTS method but has less performance degradation.
Xina ZHANG Xiaoni DU Chenhuang WU
A family of quaternary sequences over Z4 is defined based on the Ding-Helleseth generalized cyclotomic classes modulo pq for two distinct odd primes p and q. The linear complexity is determined by computing the defining polynomial of the sequences, which is in fact connected with the discrete Fourier transform of the sequences. The results show that the sequences possess large linear complexity and are “good” sequences from the viewpoint of cryptography.
Yun-Feng XING Xiao CHEN Ming-Xiang GUAN Zhe-Ming LU
Considering that the traditional local-world evolving network model cannot fully reflect the characteristics of real-world power grids, this Letter proposes a new evolving model based on geographical location clusters. The proposed model takes into account the geographical locations and degree values of nodes, and the growth process is in line with the characteristics of the power grid. Compared with the characteristics of real-world power grids, the results show that the proposed model can simulate the degree distribution of China's power grids when the number of nodes is small. When the number of nodes exceeds 800, our model can simulate the USA western power grid's degree distribution. And the average distances and clustering coefficients of the proposed model are close to that of the real world power grids. All these properties confirm the validity and rationality of our model.
Qian DENG Li GUO Chao DONG Jiaru LIN Xueyan CHEN
In this paper, we propose a low-complexity widely-linear minimum mean square error (WL-MMSE) signal detection based on the Chebyshev polynomials accelerated symmetric successive over relaxation (SSORcheb) algorithm for uplink (UL) over-loaded large-scale multiple-input multiple-output (MIMO) systems. The technique of utilizing Chebyshev acceleration not only speeds up the convergence rate significantly, and maximizes the data throughput, but also reduces the cost. By utilizing the random matrix theory, we present good estimates for the Chebyshev acceleration parameters of the proposed signal detection in real large-scale MIMO systems. Simulation results demonstrate that the new WL-SSORcheb-MMSE detection not only outperforms the recently proposed linear iterative detection, and the optimal polynomial expansion (PE) WL-MMSE detection, but also achieves a performance close to the exact WL-MMSE detection. Additionally, the proposed detection offers superior sum rate and bit error rate (BER) performance compared to the precision MMSE detection with substantially fewer arithmetic operations in a short coherence time. Therefore, the proposed detection can satisfy the high-density and high-mobility requirements of some of the emerging wireless networks, such as, the high-mobility Internet of Things (IoT) networks.
This paper reports the development of a landmine visualization system based on complex-valued self-organizing map (CSOM) by employing one-dimensional (1-D) array of taper-walled tapered slot antennas (TSAs). Previously we constructed a high-density two-dimensional array system to observe and classify complex-amplitude texture of scattered wave. The system has superiority in its adaptive distinction ability between landmines and other clutters. However, it used so many (144) antenna elements with many mechanical radio-frequency (RF) switches and cables that it has difficulty in its maintenance and also requires long measurement time. The 1-D array system proposed here uses only 12 antennas and adopts electronic RF switches, resulting in easy maintenance and 1/4 measurement time. Though we observe stripe noise specific to this 1-D system, we succeed in visualization with effective solutions.
Sun-Mi PARK Ku-Young CHANG Dowon HONG Changho SEO
In this paper, we present a new three-way split formula for binary polynomial multiplication (PM) with five recursive multiplications. The scheme is based on a recently proposed multievaluation and interpolation approach using field extension. The proposed PM formula achieves the smallest space complexity. Moreover, it has about 40% reduced time complexity compared to best known results. In addition, using developed techniques for PM formulas, we propose a three-way split formula for Toeplitz matrix vector product with five recursive products which has a considerably improved complexity compared to previous known one.
Viet-Hang DUONG Manh-Quan BUI Jian-Jiun DING Yuan-Shan LEE Bach-Tung PHAM Pham The BAO Jia-Ching WANG
This work presents a new approach which derives a learned data representation method through matrix factorization on the complex domain. In particular, we introduce an encoding matrix-a new representation of data-that satisfies the simplicial constraint of the projective basis matrix on the field of complex numbers. A complex optimization framework is provided. It employs the gradient descent method and computes the derivative of the cost function based on Wirtinger's calculus.
A Tikhonov regularized RLS algorithm with an exponential weighting factor, i.e., a leaky RLS (LRLS) algorithm was proposed by the author. A quadratic version of the LRLS algorithm also exists in the literature of adaptive filters. In this letter, a cubic version of the LRLS filter which is computationally efficient is proposed when the length of the adaptive filter is short. The proposed LRLS filter includes only a divide per iteration although its multiplications and additions increase in number. Simulation results show that the proposed LRLS filter is faster for its short length than the existing quadratic version of the LRLS filter.
Qi ZHANG Pei WANG Jun ZHU Bin TANG
A fast parameter estimation method with a coarse estimation and a fine estimation for polyphase P coded signals is proposed. For a received signal with N sampling points, the proposed method has an improved performance when the signal-to-noise ratio (SNR) is larger than 2dB and a lower computational complexity O(N logs N) compared with the latest time-frequency rate estimation method whose computational complexity is O(N2).