OpenRaiser/Intern-Atlas huggingface dataset:
On the Exact Distribution of the Scaled Largest Eigenvalue
Venue: arXiv cs.IT 2012
Year: 2012

In this paper we study the distribution of the scaled largest eigenvalue of complexWishart matrices, which has diverse applications both in statistics and wireless communications. Exact expressions, valid for any matrix dimensions, have been derived for the probability density function and the cumulative distribution function. The derived results involve only finite sums of polynomials. These results are obtained by taking advantage of properties of the Mellin transform for products of independent random variables.
On Coding Efficiency for Flash Memories
Venue: arXiv cs.IT 2012
Year: 2012

Recently, flash memories have become a competitive solution for mass storage. The flash memories have rather different properties compared with the rotary hard drives. That is, the writing of flash memories is constrained, and flash memories can endure only limited numbers of erases. Therefore, the design goals for the flash memory systems are quite different from these for other memory systems. In this paper, we consider the problem of coding efficiency. We define the "coding-efficiency" as the amount of information that one flash memory cell can be used to record per cost. Because each flash memory cell can endure a roughly fixed number of erases, the cost of data recording can be well-defined. We define "payload" as the amount of information that one flash memory cell can represent at a particular moment. By using information-theoretic arguments, we prove a coding theorem for achievable coding rates. We prove an upper and lower bound for coding efficiency. We show in this paper that there exists a fundamental trade-off between "payload" and "coding efficiency". The results in this paper may provide useful insights on the design of future flash memory systems.
On The Performance of Random Block Codes over Finite-State Fading Channels
Venue: arXiv cs.IT 2012
Year: 2012

As the mobile application landscape expands, wireless networks are tasked with supporting various connection profiles, including real-time communications and delay-sensitive traffic. Among many ensuing engineering challenges is the need to better understand the fundamental limits of forward error correction in non-asymptotic regimes. This article seeks to characterize the performance of block codes over finite-state channels with memory. In particular, classical results from information theory are revisited in the context of channels with rate transitions, and bounds on the probabilities of decoding failure are derived for random codes. This study offers new insights about the potential impact of channel correlation over time on overall performance.
Reverse Compute and Forward: A Low-Complexity Architecture for Downlink Distributed Antenna Systems
Venue: arXiv cs.IT 2012
Year: 2012

We consider a distributed antenna system where $L$ antenna terminals (ATs) are connected to a Central Processor (CP) via digital error-free links of finite capacity $R_0$, and serve $L$ user terminals (UTs). This system model has been widely investigated both for the uplink and the downlink, which are instances of the general multiple-access relay and broadcast relay networks. In this work we focus on the downlink, and propose a novel downlink precoding scheme nicknamed "Reverse Quantized Compute and Forward" (RQCoF). For this scheme we obtain achievable rates and compare with the state of the art available in the literature. We also provide simulation results for a realistic network with fading and pathloss with $K > L$ UTs, and show that channel-based user selection produces large benefits and essentially removes the problem of rank deficiency in the system matrix.
Practical Conditions for Well-behaved-ness of Anisotropic Voronoi Diagrams
Venue: arXiv cs.CG 2012
Year: 2012

Recently, simple conditions for well-behaved-ness of anisotropic Voronoi diagrams have been proposed. While these conditions ensure well-behaved-ness of two types of practical anisotropic Voronoi diagrams, as well as the geodesic-distance one, in any dimension, they are both prohibitively expensive to evaluate, and not well-suited for typical problems in approximation or optimization. We propose simple conditions that can be efficiently evaluated, and are better suited to practical problems of approximation and optimization. The practical utility of this analysis is enhanced by the fact that orphan-free anisotropic Voronoi diagrams have embedded triangulations as duals.
On Marton's inner bound for broadcast channels
Venue: arXiv cs.IT 2012
Year: 2012

Marton's inner bound is the best known achievable region for a general discrete memoryless broadcast channel. To compute Marton's inner bound one has to solve an optimization problem over a set of joint distributions on the input and auxiliary random variables. The optimizers turn out to be structured in many cases. Finding properties of optimizers not only results in efficient evaluation of the region, but it may also help one to prove factorization of Marton's inner bound (and thus its optimality). The first part of this paper formulates this factorization approach explicitly and states some conjectures and results along this line. The second part of this paper focuses primarily on the structure of the optimizers. This section is inspired by a new binary inequality that recently resulted in a very simple characterization of the sum-rate of Marton's inner bound for binary input broadcast channels. This prompted us to investigate whether this inequality can be extended to larger cardinality input alphabets. We show that several of the results for the binary input case do carry over for higher cardinality alphabets and we present a collection of results that help restrict the search space of probability distributions to evaluate the boundary of Marton's inner bound in the general case. We also prove a new inequality for the binary skew-symmetric broadcast channel that yields a very simple characterization of the entire Marton inner bound for this channel.
Compressive binary search
Venue: arXiv cs.IT 2012
Year: 2012

In this paper we consider the problem of locating a nonzero entry in a high-dimensional vector from possibly adaptive linear measurements. We consider a recursive bisection method which we dub the compressive binary search and show that it improves on what any nonadaptive method can achieve. We also establish a non-asymptotic lower bound that applies to all methods, regardless of their computational complexity. Combined, these results show that the compressive binary search is within a double logarithmic factor of the optimal performance.
Directed Information on Abstract spaces: Properties and Extremum Problems
Venue: arXiv cs.IT 2012
Year: 2012

This paper describes a framework in which directed information is defined on abstract spaces. The framework is employed to derive properties of directed information such as convexity, concavity, lower semicontinuity, by using the topology of weak convergence of probability measures on Polish spaces. Two extremum problems of directed information related to capacity of channels with memory and feedback, and non-anticipative and sequential rate distortion are analyzed showing existence of maximizing and minimizing distributions, respectively.
A New Random Coding Technique that Generalizes Superposition Coding and Binning
Venue: arXiv cs.IT 2012
Year: 2012

Proving capacity for networks without feedback or cooperation usually involves two fundamental random coding techniques: superposition coding and binning. Although conceptually very different, these two techniques often achieve the same performance, suggesting an underlying similarity. In this correspondence we propose a new random coding technique that generalizes superposition coding and binning and provides new insight on relationship among the two With this new theoretical tool, we derive new achievable regions for three classical information theoretical models: multi-access channel, broadcast channel, the interference channel, and show that, unfortunately, it does not improve over the largest known achievable regions for these cases.
On the Capacity of a General Multiple-Access Channel and of a Cognitive Network in the Very Strong Interference Regime
Venue: arXiv cs.IT 2012
Year: 2012

The capacity of the multiple-access channel with any distribution of messages among the transmitting nodes was determined by Han in 1979 and the expression of the capacity region contains a number of rate bounds and that grows exponentially with the number of messages. We derive a more compact expression for the capacity region of this channel in which the number of rate bounds depends on the distribution of the messages at the encoders. Using this expression we prove capacity for a class of general cognitive network that we denote as "very strong interference" regime. In this regime there is no rate loss in having all the receivers decode all the messages and the capacity region reduces to the capacity of the compound multiple-access channel. This result generalizes the "very strong interference" capacity results for the interference channel, the cognitive interference channel, the interference channel with a cognitive relay and many others.
Bundling Customers: How to Exploit Trust Among Customers to Maximize Seller Profit
Venue: arXiv cs.GT 2012
Year: 2012

We consider an auction of identical digital goods to customers whose valuations are drawn independently from known distributions. Myerson's classic result identifies the truthful mechanism that maximizes the seller's expected profit. Under the assumption that in small groups customers can learn each others' valuations, we show how Myerson's result can be improved to yield a higher payoff to the seller using a mechanism that offers groups of customers to buy bundles of items.
Spatially-Coupled Binary MacKay-Neal Codes for Channels with Non-Binary Inputs and Affine Subspace Outputs
Venue: arXiv cs.IT 2012
Year: 2012

We study LDPC codes for the channel with $2^m$-ary input $\underline{x}\in \mathbb{F}_2^m$ and output $\underline{y}=\underline{x}+\underline{z}\in \mathbb{F}_2^m$. The receiver knows a subspace $V\subset \mathbb{F}_2^m$ from which $\underline{z}=\underline{y}-\underline{x}$ is uniformly chosen. Or equivalently, the receiver receives an affine subspace $\underline{y}-V$ where $\underline{x}$ lies. We consider a joint iterative decoder involving the channel detector and the LDPC decoder. The decoding system considered in this paper can be viewed as a simplified model of the joint iterative decoder over non-binary modulated signal inputs e.g., $2^m$-QAM. We evaluate the performance of binary spatially-coupled MacKay-Neal codes by density evolution. The iterative decoding threshold is seriously degraded by increasing $m$. EXIT-like function curve calculations reveal that this degradation is caused by wiggles and can be mitigated by increasing the randomized window size. The resultant iterative decoding threshold values are very close to the Shannon limit.
Building a Framework for Predictive Science
Venue: arXiv cs.MS 2012
Year: 2012

Key questions that scientists and engineers typically want to address can be formulated in terms of predictive science. Questions such as: "How well does my computational model represent reality?", "What are the most important parameters in the problem?", and "What is the best next experiment to perform?" are fundamental in solving scientific problems. Mystic is a framework for massively-parallel optimization and rigorous sensitivity analysis that enables these motivating questions to be addressed quantitatively as global optimization problems. Often realistic physics, engineering, and materials models may have hundreds of input parameters, hundreds of constraints, and may require execution times of seconds or longer. In more extreme cases, realistic models may be multi-scale, and require the use of high-performance computing clusters for their evaluation. Predictive calculations, formulated as a global optimization over a potential surface in design parameter space, may require an already prohibitively large simulation to be performed hundreds, if not thousands, of times. The need to prepare, schedule, and monitor thousands of model evaluations, and dynamically explore and analyze results, is a challenging problem that requires a software infrastructure capable of distributing and managing computations on large-scale heterogeneous resources. In this paper, we present the design behind an optimization framework, and also a framework for heterogeneous computing, that when utilized together, can make computationally intractable sensitivity and optimization problems much more tractable.
Mutual-Information Optimized Quantization for LDPC Decoding of Accurately Modeled Flash Data
Venue: arXiv cs.IT 2012
Year: 2012

High-capacity NAND flash memories use multi-level cells (MLCs) to store multiple bits per cell and achieve high storage densities. Higher densities cause increased raw bit error rates (BERs), which demand powerful error correcting codes. Low-density parity-check (LDPC) codes are a well-known class of capacity-approaching codes in AWGN channels. However, LDPC codes traditionally use soft information while the flash read channel provides only hard information. Low resolution soft information may be obtained by performing multiple reads per cell with distinct word-line voltages. We select the values of these word-line voltages to maximize the mutual information between the input and output of the equivalent multiple-read channel under any specified noise model. Our results show that maximum mutual-information (MMI) quantization provides better soft information for LDPC decoding given the quantization level than the constant-pdf-ratio quantization approach. We also show that adjusting the LDPC code degree distribution for the quantized setting provides a significant performance improvement.
Verifiable Computation with Massively Parallel Interactive Proofs
Venue: arXiv cs.DC 2012
Year: 2012

As the cloud computing paradigm has gained prominence, the need for verifiable computation has grown increasingly urgent. The concept of verifiable computation enables a weak client to outsource difficult computations to a powerful, but untrusted, server. Protocols for verifiable computation aim to provide the client with a guarantee that the server performed the requested computations correctly, without requiring the client to perform the computations herself. By design, these protocols impose a minimal computational burden on the client. However, existing protocols require the server to perform a large amount of extra bookkeeping in order to enable a client to easily verify the results. Verifiable computation has thus remained a theoretical curiosity, and protocols for it have not been implemented in real cloud computing systems. Our goal is to leverage GPUs to reduce the server-side slowdown for verifiable computation. To this end, we identify abundant data parallelism in a state-of-the-art general-purpose protocol for verifiable computation, originally due to Goldwasser, Kalai, and Rothblum, and recently extended by Cormode, Mitzenmacher, and Thaler. We implement this protocol on the GPU, obtaining 40-120x server-side speedups relative to a state-of-the-art sequential implementation. For benchmark problems, our implementation reduces the slowdown of the server to factors of 100-500x relative to the original computations requested by the client. Furthermore, we reduce the already small runtime of the client by 100x. Similarly, we obtain 20-50x server-side and client-side speedups for related protocols targeted at specific streaming problems. We believe our results demonstrate the immediate practicality of using GPUs for verifiable computation, and more generally that protocols for verifiable computation have become sufficiently mature to deploy in real cloud computing systems.
Investigation to implicate data on clouds
Venue: arXiv cs.NI 2012
Year: 2012

Cloud computing can and does mean different things to different people. The common characteristics most shares are on-demand secure access to metered services from nearly anywhere and dislocation of data from inside to outside the organization. Vision of cloud computing as a new IT procurement model. The system lifecycle, risks that are identified must be carefully balanced against the security and privacy controls available and the expected benefits from their utilization. Too many controls can be inefficient and ineffective, if the benefits outweigh the costs and associated risks. In this micro research, we characterize the problems related to security challenges.
Optimization in SMT with LA(Q) Cost Functions
Venue: arXiv cs.AI 2012
Year: 2012

In the contexts of automated reasoning and formal verification, important decision problems are effectively encoded into Satisfiability Modulo Theories (SMT). In the last decade efficient SMT solvers have been developed for several theories of practical interest (e.g., linear arithmetic, arrays, bit-vectors). Surprisingly, very few work has been done to extend SMT to deal with optimization problems; in particular, we are not aware of any work on SMT solvers able to produce solutions which minimize cost functions over arithmetical variables. This is unfortunate, since some problems of interest require this functionality. In this paper we start filling this gap. We present and discuss two general procedures for leveraging SMT to handle the minimization of LA(Q) cost functions, combining SMT with standard minimization techniques. We have implemented the proposed approach within the MathSAT SMT solver. Due to the lack of competitors in AR and SMT domains, we experimentally evaluated our implementation against state-of-the-art tools for the domain of linear generalized disjunctive programming (LGDP), which is closest in spirit to our domain, on sets of problems which have been previously proposed as benchmarks for the latter tools. The results show that our tool is very competitive with, and often outperforms, these tools on these problems, clearly demonstrating the potential of the approach.
Optimization in Multi-Frequency Interferometry Ranging: Theory and Experiment
Venue: arXiv cs.IT 2012
Year: 2012

Multi-frequency interferometry (MFI) is well known as an accurate phase-based measurement scheme. The paper reveals the inherent relationship of the unambiguous measurement range (UMR), the outlier probability, the MSE performance with the frequency pattern in MFI system, and then provides the corresponding criterion for choosing the frequency pattern. We point out that the theoretical rigorous UMR of MFI deduced in the literature is usually optimistic for practical application and derive a more practical expression . It is found that the least-square (LS) estimator of MFI has a distinguished "double threshold effect". Distinct difference is observed for the MSE in moderate and high signal-to-noise ratio (SNR) region (denoted by MMSE and HMSE respectively) and the second threshold effect occurs during the rapid transition from MMSE to HMSE with increasing SNR. The closed-form expressions for the MMSE, HMSE and Cramer-Rao bound (CRB) are further derived, with HMSE coinciding with CRB. Since the HMSE is insensitive to frequency pattern, we focus on MMSE minimization by proper frequency optimization. We show that a prime-based frequency interval can be exploited for the purpose of both outlier suppression and UMR extension and design a special optimal rearrangement for any set of frequency interval, in the sense of MMSE minimization. An extremely simple frequency design method is finally developed. Simulation and field experiment verified that the proposed scheme considerably outperforms the existing method in UMR as well as MSE performance, especially in the transition from MMSE to HMSE, for Gaussian and non-Gaussian channel.
On the Transient Behavior of CHOKe
Venue: arXiv cs.NI 2012
Year: 2012

CHOKe is a simple and stateless active queue management (AQM) scheme. Apart from low operational overhead, a highly attractive property of CHOKe is that it can protect responsive TCP flows from unresponsive UDP flows. Particularly, previous works have proven that CHOKe is able to bound both bandwidth share and buffer share of (a possible aggregate) UDP traffic (flow) on a link. However, these studies consider, and pertain only to, a steady state where the queue reaches equilibrium in the presence of many (long-lived) TCP flows and an unresponsive UDP flow of fixed arrival rate. If the steady state conditions are perturbed, particularly when UDP traffic rate changes over time, it is unclear whether the protection property of CHOKe still holds. Indeed, it can be examined, for example, that when UDP rate suddenly becomes 0 (i.e., flow stops), the unresponsive flow may assume close to full utilization in sub-RTT scales, potentially starving out the TCP flows. To explain this apparent discrepancy, this paper investigates CHOKe queue properties in a transient regime, which is the time period of transition between two steady states of the queue, initiated when the rate of the unresponsive flow changes. Explicit expressions that characterize flow throughputs in transient regimes are derived. These results provide additional understanding of CHOKe, and give some explanation on its intriguing behavior in the transient regime.
Send Mixed Signals -- Earn More, Work Less
Venue: arXiv cs.GT 2012
Year: 2012

Emek et al. presented a model of probabilistic single-item second price auctions where an auctioneer who is informed about the type of an item for sale, broadcasts a signal about this type to uninformed bidders. They proved that finding the optimal (for the purpose of generating revenue) {\em pure} signaling scheme is strongly NP-hard. In contrast, we prove that finding the optimal {\em mixed} signaling scheme can be done in polynomial time using linear programming. For the proof, we show that the problem is strongly related to a problem of optimally bundling divisible goods for auctioning. We also prove that a mixed signaling scheme can in some cases generate twice as much revenue as the best pure signaling scheme and we prove a generally applicable lower bound on the revenue generated by the best mixed signaling scheme.
Channel Estimation Study for Block - Pilot Insertion in OFDM Systems under Slowly Time Varying Conditions
Venue: arXiv cs.OH 2012
Year: 2012

In this paper, we propose a study of performance of the channel estimation using LS, MMSE, LMMSE and Lr-LMMSE algorithms in OFDM (Orthogonal Frequency Division Multiplexing) system which, as known suffers from the time variation of the channel under high mobility conditions, using block pilot insertion. The loss of sub channel orthogonality leads to inter-carrier interference (ICI). Using many algorithms for channel estimation, we will show that, for a 16- QAM modulation, the LMMSE algorithm performs well to achieve this estimation but when the SNR (Signal Noise Rate) is high, the four algorithms (LS, MMSE, LMMSE and Lr-LMMSE) perform similarly, this is not always the case for another scheme of modulation. We will improve also the mean squared error for these algorithms. It will be illustrious in this paper that the LMMSE algorithm performs well with the block- pilot insertion as well as its low rank version which behave very good even when the size of FFT is very high.