OpenRaiser/Intern-Atlas huggingface dataset:
Iterative Decoding of LDPC Codes over the q-ary Partial Erasure Channel
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, we develop a new channel model, which we name the $q$-ary partial erasure channel (QPEC). The QPEC has a $q$-ary input, and its output is either the input symbol or a set of $M$ ($2 \le M \le q$) symbols, containing the input symbol. This channel serves as a generalization to the binary erasure channel, and mimics situations when a symbol output from the channel is known only partially, that is, the output symbol contains some ambiguity, but is not fully erased. This type of channel is motivated by non-volatile memory multi-level read channels. In such channels the readout is obtained by a sequence of current/voltage measurements, which may terminate with partial knowledge of the stored level. Our investigation is concentrated on the performance of low-density parity-check (LDPC) codes when used over this channel, thanks to their low decoding complexity using belief propagation. We provide the exact QPEC density-evolution equations that govern the decoding process, and suggest a cardinality-based approximation as a proxy. We then provide several bounds and approximations on the proxy density evolutions, and verify their tightness through numerical experiments. Finally, we provide tools for the practical design of LDPC codes for use over the QPEC.
Fast Parallel Operations on Search Trees
Venue: arXiv cs.DS 2016
Year: 2016

Using (a,b)-trees as an example, we show how to perform a parallel split with logarithmic latency and parallel join, bulk updates, intersection, union (or merge), and (symmetric) set difference with logarithmic latency and with information theoretically optimal work. We present both asymptotically optimal solutions and simplified versions that perform well in practice - they are several times faster than previous implementations.
Binary Speaker Embedding
Venue: arXiv cs.SD 2016
Year: 2016

The popular i-vector model represents speakers as low-dimensional continuous vectors (i-vectors), and hence it is a way of continuous speaker embedding. In this paper, we investigate binary speaker embedding, which transforms i-vectors to binary vectors (codes) by a hash function. We start from locality sensitive hashing (LSH), a simple binarization approach where binary codes are derived from a set of random hash functions. A potential problem of LSH is that the randomly sampled hash functions might be suboptimal. We therefore propose an improved Hamming distance learning approach, where the hash function is learned by a variable-sized block training that projects each dimension of the original i-vectors to variable-sized binary codes independently. Our experiments show that binary speaker embedding can deliver competitive or even better results on both speaker verification and identification tasks, while the memory usage and the computation cost are significantly reduced.
Proof equivalence in MLL is PSPACE-complete
Venue: arXiv cs.LO 2016
Year: 2016

MLL proof equivalence is the problem of deciding whether two proofs in multiplicative linear logic are related by a series of inference permutations. It is also known as the word problem for star-autonomous categories. Previous work has shown the problem to be equivalent to a rewiring problem on proof nets, which are not canonical for full MLL due to the presence of the two units. Drawing from recent work on reconfiguration problems, in this paper it is shown that MLL proof equivalence is PSPACE-complete, using a reduction from Nondeterministic Constraint Logic. An important consequence of the result is that the existence of a satisfactory notion of proof nets for MLL with units is ruled out (under current complexity assumptions). The PSPACE-hardness result extends to equivalence of normal forms in MELL without units, where the weakening rule for the exponentials induces a similar rewiring problem.
Synthesizing least-limiting guidelines for safety of semi-autonomous systems
Venue: arXiv cs.SY 2016
Year: 2016

We consider the problem of synthesizing safe-by-design control strategies for semi-autonomous systems. Our aim is to address situations when safety cannot be guaranteed solely by the autonomous, controllable part of the system and a certain level of collaboration is needed from the uncontrollable part, such as the human operator. In this paper, we propose a systematic solution to generating least-limiting guidelines, i.e. the guidelines that restrict the human operator as little as possible in the worst-case long-term system executions. The algorithm leverages ideas from 2-player turn-based games.
Fusing Loop and GPS Probe Measurements to Estimate Freeway Density
Venue: arXiv cs.SY 2016
Year: 2016

In an age of ever-increasing penetration of GPS-enabled mobile devices, the potential of real-time "probe" location information for estimating the state of transportation networks is receiving increasing attention. Much work has been done on using probe data to estimate the current speed of vehicle traffic (or equivalently, trip travel time). While travel times are useful to individual drivers, the state variable for a large class of traffic models and control algorithms is vehicle density. Our goal is to use probe data to supplement traditional, fixed-location loop detector data for density estimation. To this end, we derive a method based on Rao-Blackwellized particle filters, a sequential Monte Carlo scheme. We present a simulation where we obtain a 30\% reduction in density mean absolute percentage error from fusing loop and probe data, vs. using loop data alone. We also present results using real data from a 19-mile freeway section in Los Angeles, California, where we obtain a 31\% reduction. In addition, our method's estimate when using only the real-world probe data, and no loop data, outperformed the estimate produced when only loop data were used (an 18\% reduction). These results demonstrate that probe data can be used for traffic density estimation.
Capacity of the Gaussian Two-Hop Full-Duplex Relay Channel with Residual Self-Interference
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, we investigate the capacity of the Gaussian two-hop full-duplex (FD) relay channel with residual self-interference. This channel is comprised of a source, an FD relay, and a destination, where a direct source-destination link does not exist and the FD relay is impaired by residual self-interference. We adopt the worst-case linear self-interference model with respect to the channel capacity, and model the residual self-interference as a Gaussian random variable whose variance depends on the amplitude of the transmit symbol of the relay. For this channel, we derive the capacity and propose an explicit capacity-achieving coding scheme. Thereby, we show that the optimal input distribution at the source is Gaussian and its variance depends on the amplitude of the transmit symbol of the relay. On the other hand, the optimal input distribution at the relay is discrete or Gaussian, where the latter case occurs only when the relay-destination link is the bottleneck link. The derived capacity converges to the capacity of the two-hop ideal FD relay channel without self-interference and to the capacity of the two-hop half-duplex (HD) relay channel in the limiting cases when the residual self-interference is zero and infinite, respectively. Our numerical results show that significant performance gains are achieved with the proposed capacity-achieving coding scheme compared to the achievable rates of conventional HD relaying and/or conventional FD relaying.
Private Webmail 2.0: Simple and Easy-to-Use Secure Email
Venue: arXiv cs.CR 2016
Year: 2016

Private Webmail 2.0 (Pwm 2.0) improves upon the current state of the art by increasing the usability and practical security of secure email for ordinary users. More users are able to send and receive encrypted emails without mistakenly revealing sensitive information. In this paper we describe user interface traits that positively affect the usability and security of Pwm 2.0: (1) an artificial delay to encryption that enhances user confidence in Pwm 2.0 while simultaneously instructing users on who can read their encrypted messages; (2) a modified composition interface that helps protect users from mistakenly sending sensitive information in the clear; (3) an annotated secure email composition interface that instructs users on how to correctly use secure email; and (4) inline, context-sensitive tutorials, which improved view rates for tutorials from less than 10% in earlier systems to over 90% for Pwm 2.0. In a user study involving 51 participants we validate these interface modifications, and also show that the use of manual encryption has no effect on usability or security.
An Asymptotic Approximation of TCP CUBIC
Venue: arXiv cs.NI 2016
Year: 2016

In this paper, we derive an expression for computing average window size of a single TCP CUBIC connection under random losses. Throughput expression for TCP CUBIC has been computed earlier under deterministic periodic packet losses. We validate this expression theoretically. We then use insights from the deterministic loss based model to derive an expression for computing average window size of a single TCP CUBIC connection under random losses. For this computation, we first consider the sequence of TCP CUBIC window evolution processes indexed by the drop rate, p and show that with a suitable scaling this sequence converges to a limiting Markov chain as p tends to 0. The stationary distribution of the limiting Markov chain is then used to derive the average window size for small packet error rates. We validate our model and approximations via simulations.
Build your own clarithmetic I: Setup and completeness
Venue: arXiv cs.LO 2016
Year: 2016

Clarithmetics are number theories based on computability logic (see http://www.csc.villanova.edu/~japaridz/CL/ ). Formulas of these theories represent interactive computational problems, and their "truth" is understood as existence of an algorithmic solution. Various complexity constraints on such solutions induce various versions of clarithmetic. The present paper introduces a parameterized/schematic version CLA11(P1,P2,P3,P4). By tuning the three parameters P1,P2,P3 in an essentially mechanical manner, one automatically obtains sound and complete theories with respect to a wide range of target tricomplexity classes, i.e. combinations of time (set by P3), space (set by P2) and so called amplitude (set by P1) complexities. Sound in the sense that every theorem T of the system represents an interactive number-theoretic computational problem with a solution from the given tricomplexity class and, furthermore, such a solution can be automatically extracted from a proof of T. And complete in the sense that every interactive number-theoretic problem with a solution from the given tricomplexity class is represented by some theorem of the system. Furthermore, through tuning the 4th parameter P4, at the cost of sacrificing recursive axiomatizability but not simplicity or elegance, the above extensional completeness can be strengthened to intensional completeness, according to which every formula representing a problem with a solution from the given tricomplexity class is a theorem of the system. This article is published in two parts. The present Part I introduces the system and proves its completeness, while Part II is devoted to proving soundness.
Strong Secrecy and Stealth for Broadcast Channels with Confidential Messages
Venue: arXiv cs.IT 2016
Year: 2016

We consider a discrete memoryless broadcast channel consists of two users and a sender. The sender has two independent confidential messages for each user. We extend the work of Liu et al.\ on broadcast channels with two confidential messages with weak secrecy criterion to strong secrecy. Our results are based on an extension of the techniques developed by Hou and Kramer on bounding Kullback-Leibler divergence in context of \textit{resolvability} and \textit{effective secrecy}.
Most Complex Regular Ideal Languages
Venue: arXiv cs.FL 2016
Year: 2016

A right ideal (left ideal, two-sided ideal) is a non-empty language $L$ over an alphabet $Σ$ such that $L=LΣ^*$ ($L=Σ^*L$, $L=Σ^*LΣ^*$). Let $k=3$ for right ideals, 4 for left ideals and 5 for two-sided ideals. We show that there exist sequences ($L_n \mid n \ge k $) of right, left, and two-sided regular ideals, where $L_n$ has quotient complexity (state complexity) $n$, such that $L_n$ is most complex in its class under the following measures of complexity: the size of the syntactic semigroup, the quotient complexities of the left quotients of $L_n$, the number of atoms (intersections of complemented and uncomplemented left quotients), the quotient complexities of the atoms, and the quotient complexities of reversal, star, product (concatenation), and all binary boolean operations. In that sense, these ideals are "most complex" languages in their classes, or "universal witnesses" to the complexity of the various operations.
Detection of Faults in Rotating Machinery Using Periodic Time-Frequency Sparsity
Venue: arXiv cs.SD 2016
Year: 2016

This paper addresses the problem of extracting periodic oscillatory features in vibration sig- nals for detecting faults in rotating machinery. To extract the feature, we propose an approach in the short-time Fourier transform (STFT) domain where the periodic oscillatory feature man- ifests itself as a relatively sparse grid. To estimate the sparse grid, we formulate an optimization problem using customized binary weights in the regularizer, where the weights are formulated to promote periodicity. In order to solve the proposed optimization problem, we develop an algorithm called augmented Lagrangian majorization-minimization algorithm, which combines the split augmented Lagrangian shrinkage algorithm (SALSA) with majorization-minimization (MM), and is guaranteed to converge for both convex and non-convex formulation. As examples, the proposed approach is applied to simulated data, and used as a tool for diagnosing faults in bearings and gearboxes for real data, and compared to some state-of-the-art methods. The results show the proposed approach can effectively detect and extract the periodical oscillatory features.
Large-Scale Analysis of the Accuracy of the Journal Classification Systems of Web of Science and Scopus
Venue: arXiv cs.DL 2016
Year: 2016

Journal classification systems play an important role in bibliometric analyses. The two most important bibliographic databases, Web of Science and Scopus, each provide a journal classification system. However, no study has systematically investigated the accuracy of these classification systems. To examine and compare the accuracy of journal classification systems, we define two criteria on the basis of direct citation relations between journals and categories. We use Criterion I to select journals that have weak connections with their assigned categories, and we use Criterion II to identify journals that are not assigned to categories with which they have strong connections. If a journal satisfies either of the two criteria, we conclude that its assignment to categories may be questionable. Accordingly, we identify all journals with questionable classifications in Web of Science and Scopus. Furthermore, we perform a more in-depth analysis for the field of Library and Information Science to assess whether our proposed criteria are appropriate and whether they yield meaningful results. It turns out that according to our citation-based criteria Web of Science performs significantly better than Scopus in terms of the accuracy of its journal classification system.
Do Prices Coordinate Markets?
Venue: arXiv cs.GT 2016
Year: 2016

Walrasian equilibrium prices can be said to coordinate markets: They support a welfare optimal allocation in which each buyer is buying bundle of goods that is individually most preferred. However, this clean story has two caveats. First, the prices alone are not sufficient to coordinate the market, and buyers may need to select among their most preferred bundles in a coordinated way to find a feasible allocation. Second, we don't in practice expect to encounter exact equilibrium prices tailored to the market, but instead only approximate prices, somehow encoding "distributional" information about the market. How well do prices work to coordinate markets when tie-breaking is not coordinated, and they encode only distributional information? We answer this question. First, we provide a genericity condition such that for buyers with Matroid Based Valuations, overdemand with respect to equilibrium prices is at most 1, independent of the supply of goods, even when tie-breaking is done in an uncoordinated fashion. Second, we provide learning-theoretic results that show that such prices are robust to changing the buyers in the market, so long as all buyers are sampled from the same (unknown) distribution.
Decomposition into Low-rank plus Additive Matrices for Background/Foreground Separation: A Review for a Comparative Evaluation with a Large-Scale Dataset
Venue: arXiv cs.CV 2016
Year: 2016

Recent research on problem formulations based on decomposition into low-rank plus sparse matrices shows a suitable framework to separate moving objects from the background. The most representative problem formulation is the Robust Principal Component Analysis (RPCA) solved via Principal Component Pursuit (PCP) which decomposes a data matrix in a low-rank matrix and a sparse matrix. However, similar robust implicit or explicit decompositions can be made in the following problem formulations: Robust Non-negative Matrix Factorization (RNMF), Robust Matrix Completion (RMC), Robust Subspace Recovery (RSR), Robust Subspace Tracking (RST) and Robust Low-Rank Minimization (RLRM). The main goal of these similar problem formulations is to obtain explicitly or implicitly a decomposition into low-rank matrix plus additive matrices. In this context, this work aims to initiate a rigorous and comprehensive review of the similar problem formulations in robust subspace learning and tracking based on decomposition into low-rank plus additive matrices for testing and ranking existing algorithms for background/foreground separation. For this, we first provide a preliminary review of the recent developments in the different problem formulations which allows us to define a unified view that we called Decomposition into Low-rank plus Additive Matrices (DLAM). Then, we examine carefully each method in each robust subspace learning/tracking frameworks with their decomposition, their loss functions, their optimization problem and their solvers. Furthermore, we investigate if incremental algorithms and real-time implementations can be achieved for background/foreground separation. Finally, experimental results on a large-scale dataset called Background Models Challenge (BMC 2012) show the comparative performance of 32 different robust subspace learning/tracking methods.
Wireless Powered Communications with Non-Orthogonal Multiple Access
Venue: arXiv cs.IT 2016
Year: 2016

We study a wireless-powered uplink communication system with non-orthogonal multiple access (NOMA), consisting of one base station and multiple energy harvesting users. More specifically, we focus on the individual data rate optimization and fairness improvement and we show that the formulated problems can be optimally and efficiently solved by either linear programming or convex optimization. In the provided analysis, two types of decoding order strategies are considered, namely fixed decoding order and time- sharing. Furthermore, we propose an efficient greedy algorithm, which is suitable for the practical implementation of the time-sharing strategy. Simulation results illustrate that the proposed scheme outperforms the baseline orthogonal multiple access scheme. More specifically, it is shown that NOMA offers a considerable improvement in throughput, fairness, and energy efficiency. Also, the dependence among system throughput, minimum individual data rate, and harvested energy is revealed, as well as an interesting trade-off between rates and energy efficiency. Finally, the convergence speed of the proposed greedy algorithm is evaluated, and it is shown that the required number of iterations is linear with respect to the number of users.
About Notations in Multiway Array Processing
Venue: arXiv cs.NA 2016
Year: 2016

This paper gives an overview of notations used in multiway array processing. We redefine the vectorization and matricization operators to comply with some properties of the Kronecker product. The tensor product and Kronecker product are also represented with two different symbols, and it is shown how these notations lead to clearer expressions for multiway array operations. Finally, the paper recalls the useful yet widely unknown properties of the array normal law with suggested notations.
Enhanced Low-Rank Matrix Approximation
Venue: arXiv cs.CV 2016
Year: 2016

This letter proposes to estimate low-rank matrices by formulating a convex optimization problem with non-convex regularization. We employ parameterized non-convex penalty functions to estimate the non-zero singular values more accurately than the nuclear norm. A closed-form solution for the global optimum of the proposed objective function (sum of data fidelity and the non-convex regularizer) is also derived. The solution reduces to singular value thresholding method as a special case. The proposed method is demonstrated for image denoising.
Evaluation of the Hamming weights of a class of linear codes based on Gauss sums
Venue: arXiv cs.IT 2016
Year: 2016

Linear codes with a few weights have been widely investigated in recent years. In this paper, we mainly use Gauss sums to represent the Hamming weights of a class of $q$-ary linear codes under some certain conditions, where $q$ is a power of a prime. The lower bound of its minimum Hamming distance is obtained. In some special cases, we evaluate the weight distributions of the linear codes by semi-primitive Gauss sums and obtain some one-weight, two-weight linear codes. It is quite interesting that we find new optimal codes achieving some bounds on linear codes. The linear codes in this paper can be used in secret sharing schemes, authentication codes and data storage systems.
The expected bit complexity of the von Neumann rejection algorithm
Venue: arXiv cs.IT 2016
Year: 2016

In 1952, von Neumann introduced the rejection method for random variate generation. We revisit this algorithm when we have a source of perfect bits at our disposal. In this random bit model, there are universal lower bounds for generating a random variate with a given density to within an accuracy $ε$ derived by Knuth and Yao, and refined by the authors. In general, von Neumann's method fails in this model. We propose a modification that insures proper behavior for all Riemann-integrable densities on compact sets, and show that the expected number of random bits needed behaves optimally with respect to universal lower bounds. In particular, we introduce the notion of an oracle that evaluates the supremum and infimum of a function on any rectangle of $\mathbb{R}^{d}$, and develop a quadtree-style extension of the classical rejection method.