We show that every polynomial threshold function that sign-represents the ODD-MAXBITn function has total absolute weight 2Ω(n1/3). The bound is tight up to a logarithmic factor in the exponent.

In this letter, we consider the problem of joint selection of transmitters and receivers in a distributed multi-input multi-output radar network for localization. Different from previous works, we consider a more mathematically challenging but generalized situation that the transmitting signals are not perfectly orthogonal. Taking Cramér Rao lower bound as performance metric, we propose a scheme of joint selection of transmitters and receivers (JSTR) aiming at optimizing the localization performance under limited number of nodes. We propose a bi-convex relaxation to replace the resultant NP hard non-convex problem. Using the bi-convexity, the surrogate problem can be efficiently resolved by nonlinear alternating direction method of multipliers. Simulation results reveal that the proposed algorithm has very close performance compared with the computationally intensive but global optimal exhaustive search method.

In this paper, we consider a group testing (GT) problem. We derive a lower bound on the probability of error for successful decoding of defected binary signals. To this end, we exploit Fano's inequality theorem in the information theory. We show that the probability of error is bounded as an entropy function, a density of a pooling matrix and a sparsity of a binary signal. We evaluate that for decoding of highly sparse signals, the pooling matrix is required to be dense. Conversely, if dense signals are needed to decode, the sparse pooling matrix should be designed to achieve the small probability of error.

This paper presents an efficient acceleration algorithm for Lloyd-type k-means clustering, which is suitable to a large-scale and high-dimensional data set with potentially numerous classes. The algorithm employs a novel projection-based filter (PRJ) to avoid unnecessary distance calculations, resulting in high-speed performance keeping the same results as a standard Lloyd's algorithm. The PRJ exploits a summable lower bound on a squared distance defined in a lower-dimensional space to which data points are projected. The summable lower bound can make the bound tighter dynamically by incremental addition of components in the lower-dimensional space within each iteration although the existing lower bounds used in other acceleration algorithms work only once as a fixed filter. Experimental results on large-scale and high-dimensional real image data sets demonstrate that the proposed algorithm works at high speed and with low memory consumption when large k values are given, compared with the state-of-the-art algorithms.

In X-ray computed tomography, scattered X-rays are generally removed by using a post-patient collimator located in front of the detector. In this paper, we show that the scattered X-rays have the potential to improve the estimation accuracy of the attenuation coefficient in computed tomography. In order to clarify the problem, we simplified the geometry of the computed tomography into a thin cylinder composed of a homogeneous material so that only one attenuation coefficient needs to be estimated. We then conducted a Monte Carlo numerical experiment on improving the estimation accuracy of attenuation coefficient by measuring the scattered X-rays with several dedicated toroidal detectors around the cylinder in addition to the primary X-rays. We further present a theoretical analysis to explain the experimental results. We employed a model that uses a T-junction (i.e., T-junction model) to divide the photon transport into primary and scattered components. This division is processed with respect to the attenuation coefficient. Using several T-junction models connected in series, we modeled the case of several scatter detectors. The estimation accuracy was evaluated according to the variance of the efficient estimator, i.e., the Cramer-Rao lower bound. We confirmed that the variance decreases as the number of scatter detectors increases, which implies that using scattered X-rays can reduce the irradiation dose for patients.

In this letter, we focus on a system where N sources send n ≤ N different packets to one destination, through M ≥ N relays. Each relay employs random linear network coding to encode the packets it received by randomly choosing coefficients in a finite field Fq, then forwards it to the destination. Owing to the inherent errorprone nature of erasure channels, data packets received by the relay and the destination nodes may not be correct. We analyze the optimal throughput with respect to n, given a series of parameters and derive the upper and lower bounds of throughput performance. We also analyze the impact of the number of relays and the erasure probability on the throughput performance. Simulation results are well matched with the theoretical analysis.

The Android pattern unlock is a widely adopted graphical password system that requires a user to draw a secret pattern connecting points arranged in a grid. The theoretical security of pattern unlock can be defined by the number of possible patterns. However, only upper bounds of the number of patterns have been known except for 3×3 and 4×4 grids for which the exact number of patterns was found by brute-force enumeration. In this letter, we present the first lower bound by computing the minimum number of visible points from each point in various subgrids.

In the paradigm of network coding, when the network topology information cannot be utilized completely, random linear network coding (RLNC) is proposed as a feasible coding scheme. But since RLNC neither considers the global network topology nor coordinates codings between different nodes, it may not achieve the best possible performance of network coding. Hence, the performance analysis of RLNC is very important for both theoretical research and practical applications. Motivated by a fact that different network topology information can be available for different network communication problems, we study and obtain several upper and lower bounds on the failure probability at sink nodes depending on different network topology information in this paper, which is also the kernel to discuss some other types of network failure probabilities. In addition, we show that the obtained upper bounds are tight, the obtained lower bound is asymptotically tight, and we give the worst cases for different scenarios.

In distributed storage systems, codes with lower repair locality are much more desirable due to their superiority in reducing the disk I/O complexity of each repair process. Motivated partially by both codes with information (r,δ1)c locality and codes with cooperative (r,l) locality, we propose the concept of codes with information (r,l,δ) locality in this paper. For a linear code C with information (r,l,δ) locality, values at arbitrary l information coordinates of an information set I can be recovered by connecting any of δ existing pairwise disjoint local repair sets with size no more than r, where a local repair set of l coordinates is defined as the set of some other coordinates by which one can recover the values at these l coordinates. We derive a lower bound on the codeword length n for [n,k,d] linear codes with information (r,l,δ) locality. Furthermore, we indicate its tightness for some special cases. Particularly, some existing results can be deduced from our bound by restriction on parameters.

Explicit evaluation of the rate-distortion function has rarely been achieved when it is strictly greater than its Shannon lower bound since it requires to identify the support of the optimal reconstruction distribution. In this paper, we consider the rate-distortion function for the distortion measure defined by an ε-insensitive loss function. We first present the Shannon lower bound applicable to any source distribution with finite differential entropy. Then, focusing on the Laplacian and Gaussian sources, we prove that the rate-distortion functions of these sources are strictly greater than their Shannon lower bounds and obtain upper bounds for the rate-distortion functions. Small distortion limit and numerical evaluation of the bounds suggest that the Shannon lower bound provides a good approximation to the rate-distortion function for the ε-insensitive distortion measure. By using the derived bounds, we examine the performance of a scalar quantizer. Furthermore, we discuss variants and extensions of the ε-insensitive distortion measure and obtain lower and upper bounds for the rate-distortion function.

We present a new lower bound on the number of gates in reversible logic circuits that represent a given reversible logic function, in which the circuits are assumed to consist of general Toffoli gates and have no redundant input/output lines. We make a theoretical comparison of lower bounds, and prove that the proposed bound is better than the previous one. Moreover, experimental results for lower bounds on randomly-generated reversible logic functions and reversible benchmarks are given. The results also demonstrate that the proposed lower bound is better than the former one.

In this paper, we consider the optimization of measurement matrix in Compressed Sensing (CS) framework. Based on the boundary constraint, we propose a novel algorithm to make the “mutual coherence” approach a lower bound. This algorithm is implemented by using an iterative strategy. In each iteration, a neighborhood interval of the maximal off-diagonal entry in the Gram matrix is scaled down with the same shrinkage factor, and then a lower mutual coherence between the measurement matrix and sparsifying matrix is obtained. After many iterations, the magnitudes of most of off-diagonal entries approach the lower bound. The proposed optimization algorithm demonstrates better performance compared with other typical optimization methods, such as t-averaged mutual coherence. In addition, the effectiveness of CS can be used for the compression of complex synthetic aperture radar (SAR) image is verified, and experimental results using simulated data and real field data corroborate this claim.

In order to evaluate the goodness of frequency hopping (FH) sequence design, the periodic Hamming correlation function is used as an important measure. But aperiodic Hamming correlation of FH sequences matters in real applications, while it received little attraction in the literature compared with periodic Hamming correlation. In this paper, the new aperiodic Hamming correlation lower bounds for FH sequences, with respect to the size of the frequency slot set, the sequence length, the family size, the maximum aperiodic Hamming autocorrelation and the maximum aperiodic Hamming crosscorrelation are established. The new aperiodic bounds are tighter than the Peng-Fan bounds. In addition, the new bounds include the second powers of the maximum aperiodic Hamming autocorrelation and the maximum aperiodic Hamming crosscorrelation but the Peng-Fan bounds do not include them. For the given sequence length, the family size and the frequency slot set size, the values of the maximum aperiodic Hamming autocorrelation and the maximum aperiodic Hamming crosscorrelation are inside of an ellipse which is given by the new aperiodic bounds.

This letter presents a novel opportunistic cooperative positioning approach for orthogonal frequency-division multiple access (OFDMA) systems. The basic idea is to allow idle mobile terminals (MTs) opportunistically estimating the arrival timing of the training sequences for uplink synchronization from active MTs. The major advantage of the proposed approach over state-of-the-arts is that the positioning-related measurements among MTs are performed without the paid of training overhead. Moreover, Cramer-Rao lower bound (CRLB) is utilized to derive the positioning accuracy limit of the proposed approach, and the numerical results show that the proposed approach can improve the accuracy of non-cooperative approaches with the a-priori stochastic knowledge of clock bias among idle MTs.

To reduce the cost of fault management in all-optical networks, it is a promising approach to detect the degradation of optical signal quality solely at the terminal points of all-optical monitoring paths. The all-optical monitoring paths must be routed so that all single-link failures can be localized using route information of monitoring paths where signal quality degradation is detected. However, route computation for the all-optical monitoring paths that satisfy the above condition is time consuming. This paper proposes a procedure for deriving the lower bounds of the required number of monitoring paths to localize all single-link failures, and proposes an efficient monitoring path computation method based on the derived lower bounds. The proposed method repeats the route computation for the monitoring paths until feasible routes can be found, while the assumed number of monitoring paths increases, starting from the lower bounds. With the proposed method, the minimum number of monitoring paths with the overall shortest routes can be obtained quickly by solving several small-scale integer linear programming problems when the possible terminal nodes of monitoring paths are arbitrarily given. Thus, the proposed method can minimize the required number of monitors for detecting the degradation of signal quality and the total overhead traffic volume transferred through the monitoring paths.

This letter investigates the training convergence in range-based cooperative positioning with stochastic positional knowledge. Firstly, a closed-form of squared position-error bound (SPEB) is derived with error-free ranging. Using the derived closed-form, it is proved that the SPEB reaches its minimum when at least 2 out of N (> 2) agents send training sequences. Finally, numerical results are provided to elaborate the theoretical analysis with zero-mean Gaussian ranging errors.

Tomlinson-Harashima precoding (THP) is considered to be a prominent precoding scheme due to its ability to efficiently cancel out the known interference at the transmitter side. Therefore, the information rates achieved by THP are superior to those achieved by conventional linear precoding schemes. In this paper, new lower bounds on the achievable information rates for the regularized THP scheme are derived. Analytical results show that the lower bounds derived in this paper are tighter than the original lower bounds particularly for the low SNR range, while all lower bounds converge to as SNR ∞.

This paper presents an improved version of multi-stage threshold decoding with a difference register (MTD-DR) for self-orthogonal convolutional codes (SOCCs). An approximate lower bound on the bit error rate (BER) with the maximum likelihood (ML) decoding is also given. MTD-DR is shown to achieve an approximate lower bound of ML decoding performance at the higher Eb/N0. The code with larger minimum Hamming distance reduces the BER in error floor, but the BER in waterfall shifts to the higher Eb/N0. This paper gives a decoding scheme that improves the BER in both directions, waterfall and error floor. In the waterfall region, a 2-step decoding (2SD) improves the coding gain of 0.40 dB for shorter codes (code length 4200) and of 0.55 dB for longer codes (code length 80000) compared to the conventional MTD-DR. The 2-step decoding that serially concatenates the parity check (PC) decoding improves the BER in the error floor region. This paper gives an effective use of PC decoding, that further makes the BER 1/8 times compared to the ordinary use of PC decoding in the error floor region. Therefore, the 2SD with effective use of parity check decoding improves the BER in the waterfall and the error floor regions simultaneously.

In the localized Discrete Fourier Transform-Spread-Orthogonal Frequency Division Multiplexing (DFT-S-OFDM) uplink cooperative system, multiple carrier frequency offsets (MCFO), arising from the nodes' separate oscillators and Doppler spreads, drastically degrade the performance of the receiver. To solve the problem, this letter proposes an efficient MCFO compensation method which fully exploits the diversity gain of space frequency block coded (SFBC) and the characteristic of inter-carrier interference (ICI). Moreover, the bit error ratio (BER) lower bound of the proposed algorithm is theoretically derived. Simulation results validate the theoretical analysis and demonstrate that the proposed MCFO compensation method can achieve robust BER performance in a wide range of MCFO in the multipath Rayleigh fading channel.

For cyclic codes some well-known lower bounds and some decoding methods up to the half of the bounds are suggested. Particularly, the shift bound is a good lower bound of the minimum distance for cyclic codes, Reed-Muller codes and geometric Goppa codes. In this paper we consider cyclic codes defined by their defining set, and new simple derivation of the shift bound using the discrete Fourier transform with unknown elements and the Blahut theorem is shown. Moreover two examples of binary cyclic codes are given.