OpenRaiser/Intern-Atlas huggingface dataset:
L2 OSTC-CPM: Theory and design
Venue: arXiv cs.IT 2008
Year: 2008

The combination of space-time coding (STC) and continuous phase modulation (CPM) is an attractive field of research because both STC and CPM bring many advantages for wireless communications. Zhang and Fitz [1] were the first to apply this idea by constructing a trellis based scheme. But for these codes the decoding effort grows exponentially with the number of transmitting antennas. This was circumvented by orthogonal codes introduced by Wang and Xia [2]. Unfortunately, based on Alamouti code [3], this design is restricted to two antennas. However, by relaxing the orthogonality condition, we prove here that it is possible to design L2-orthogonal space-time codes which achieve full rate and full diversity with low decoding effort. In part one, we generalize the two-antenna code proposed by Wang and Xia [2] from pointwise to L2-orthogonality and in part two we present the first L2-orthogonal code for CPM with three antennas. In this report, we detail these results and focus on the properties of these codes. Of special interest is the optimization of the bit error rate which depends on the initial phase of the system. Our simulation results illustrate the systemic behavior of these conditions.
A logic with temporally accessible iteration
Venue: arXiv cs.LO 2008
Year: 2008

Deficiency in expressive power of the first-order logic has led to developing its numerous extensions by fixed point operators, such as Least Fixed-Point (LFP), inflationary fixed-point (IFP), partial fixed-point (PFP), etc. These logics have been extensively studied in finite model theory, database theory, descriptive complexity. In this paper we introduce unifying framework, the logic with iteration operator, in which iteration steps may be accessed by temporal logic formulae. We show that proposed logic FO+TAI subsumes all mentioned fixed point extensions as well as many other fixed point logics as natural fragments. On the other hand we show that over finite structures FO+TAI is no more expressive than FO+PFP. Further we show that adding the same machinery to the logic of monotone inductions (FO+LFP) does not increase its expressive power either.
Using rational numbers to key nested sets
Venue: arXiv cs.DB 2008
Year: 2008

This report details the generation and use of tree node ordering keys in a single relational database table. The keys for each node are calculated from the keys of its parent, in such a way that the sort order places every node in the tree before all of its descendants and after all siblings having a lower index. The calculation from parent keys to child keys is simple, and reversible in the sense that the keys of every ancestor of a node can be calculated from that node's keys without having to consult the database. Proofs of the above properties of the key encoding process and of its correspondence to a finite continued fraction form are provided.
Broadcasting with side information
Venue: arXiv cs.IT 2008
Year: 2008

A sender holds a word x consisting of n blocks x_i, each of t bits, and wishes to broadcast a codeword to m receivers, R_1,...,R_m. Each receiver R_i is interested in one block, and has prior side information consisting of some subset of the other blocks. Let β_t be the minimum number of bits that has to be transmitted when each block is of length t, and let βbe the limit β= \lim_{t \to \infty} β_t/t. In words, βis the average communication cost per bit in each block (for long blocks). Finding the coding rate β, for such an informed broadcast setting, generalizes several coding theoretic parameters related to Informed Source Coding on Demand, Index Coding and Network Coding. In this work we show that usage of large data blocks may strictly improve upon the trivial encoding which treats each bit in the block independently. To this end, we provide general bounds on β_t, and prove that for any constant C there is an explicit broadcast setting in which β= 2 but β_1 > C. One of these examples answers a question of Lubetzky and Stav. In addition, we provide examples with the following counterintuitive direct-sum phenomena. Consider a union of several mutually independent broadcast settings. The optimal code for the combined setting may yield a significant saving in communication over concatenating optimal encodings for the individual settings. This result also provides new non-linear coding schemes which improve upon the largest known gap between linear and non-linear Network Coding, thus improving the results of Dougherty, Freiling, and Zeger. The proofs use ideas related to Witsenhausen's rate, OR graph products, colorings of Cayley graphs and the chromatic numbers of Kneser graphs.
Power-Balanced Orthogonal Space-Time Block Code
Venue: arXiv cs.IT 2008
Year: 2008

In this paper, we propose two new systematic ways to construct amicable orthogonal designs (AOD), with an aim to facilitate the construction of power-balanced orthogonal spacetime block codes (O-STBC) with favorable practical attributes. We also show that an AOD can be constructed from an Amicable Family (AF), and such a construction is crucial for achieving a power-balanced O-STBC. In addition, we develop design guidelines on how to select the "type" parameter of an AOD so that the resultant O-STBC will have better power-distribution and code-coefficient attributes. Among the new O-STBCs obtained, one is shown to be optimal in terms of power distribution attributes. In addition, one of the proposed construction methods is shown to generalize some other construction methods proposed in the literature.
Limited Feedback for Multi-Antenna Multi-user Communications with Generalized Multi-Unitary Decomposition
Venue: arXiv cs.IT 2008
Year: 2008

In this paper, we propose a decomposition method called Generalized Multi-Unitary Decomposition (GMUD) which is useful in multi-user MIMO precoding. This decomposition transforms a complex matrix H into PRQ, where R is a special matrix whose first row contains only a non-zero user defined value at the left-most position, P and Q are a pair of unitary matrices. The major attraction of our proposed GMUD is we can obtain multiple solutions of P and Q >. With GMUD, we propose a precoding method for a MIMO multi-user system that does not require full channel state information (CSI) at the transmitter. The proposed precoding method uses the multiple unitary matrices property to compensate the inaccurate feedback information as the transmitter can steer the transmission beams of individual users such that the inter-user interference is kept minimum.
In Pursuit of Spreadsheet Excellence
Venue: arXiv cs.SE 2008
Year: 2008

The first fully-documented study into the quantitative impact of errors in operational spreadsheets identified an interesting anomaly. One of the five participating organisations involved in the study contributed a set of five spreadsheets of such quality that they set the organisation apart in a statistical sense. This virtuoso performance gave rise to a simple sampling test - The Clean Sheet Test - which can be used to objectively evaluate if an organisation is in control of the spreadsheets it is using in important processes such as financial reporting.
Statistical Learning of Arbitrary Computable Classifiers
Venue: arXiv cs.LG 2008
Year: 2008

Statistical learning theory chiefly studies restricted hypothesis classes, particularly those with finite Vapnik-Chervonenkis (VC) dimension. The fundamental quantity of interest is the sample complexity: the number of samples required to learn to a specified level of accuracy. Here we consider learning over the set of all computable labeling functions. Since the VC-dimension is infinite and a priori (uniform) bounds on the number of samples are impossible, we let the learning algorithm decide when it has seen sufficient samples to have learned. We first show that learning in this setting is indeed possible, and develop a learning algorithm. We then show, however, that bounding sample complexity independently of the distribution is impossible. Notably, this impossibility is entirely due to the requirement that the learning algorithm be computable, and not due to the statistical nature of the problem.
Comparative Study of SVD and QRS in Closed-Loop Beamforming Systems
Venue: arXiv cs.IT 2008
Year: 2008

We compare two closed-loop beamforming algorithms, one based on singular value decomposition (SVD) and the other based on equal diagonal QR decomposition (QRS). SVD has the advantage of parallelizing the MIMO channel, but each of the sub-channels has different gain. QRS has the advantage of having equal diagonal value for the decomposed channel, but the subchannels are not fully parallelized, hence requiring successive interference cancellation or other techniques to perform decoding. We consider a closed-loop system where the feedback information is a unitary beamforming matrix. Due to the discrete and limited modulation set, SVD may have inferior performance to QRS when no modulation set selection is performed. However, if the selection of modulation set is performed optimally, we show that SVD can outperform QRS.
Efficient and Robust Compressed Sensing using High-Quality Expander Graphs
Venue: arXiv cs.IT 2008
Year: 2008

Expander graphs have been recently proposed to construct efficient compressed sensing algorithms. In particular, it has been shown that any $n$-dimensional vector that is $k$-sparse (with $k\ll n$) can be fully recovered using $O(k\log\frac{n}{k})$ measurements and only $O(k\log n)$ simple recovery iterations. In this paper we improve upon this result by considering expander graphs with expansion coefficient beyond 3/4 and show that, with the same number of measurements, only $O(k)$ recovery iterations are required, which is a significant improvement when $n$ is large. In fact, full recovery can be accomplished by at most $2k$ very simple iterations. The number of iterations can be made arbitrarily close to $k$, and the recovery algorithm can be implemented very efficiently using a simple binary search tree. We also show that by tolerating a small penalty on the number of measurements, and not on the number of recovery iterations, one can use the efficient construction of a family of expander graphs to come up with explicit measurement matrices for this method. We compare our result with other recently developed expander-graph-based methods and argue that it compares favorably both in terms of the number of required measurements and in terms of the recovery time complexity. Finally we will show how our analysis extends to give a robust algorithm that finds the position and sign of the $k$ significant elements of an almost $k$-sparse signal and then, using very simple optimization techniques, finds in sublinear time a $k$-sparse signal which approximates the original signal with very high precision.
Scalar Quantization for Audio Data Coding
Venue: arXiv cs.MM 2008
Year: 2008

This paper is concerned with scalar quantization of transform coefficients in an audio codec. The generalized Gaussian distribution (GGD) is used as an approximation of one-dimensional probability density function for transform coefficients obtained by modulated lapped transform (MLT) or modified cosine transform (MDCT) filterbank. The rationale of the model is provided in comparison with theoretically achievable rate-distortion function. The rate-distortion function computed for the random sequence obtained from a real sequence of samples from a large database is compared with that computed for random sequence obtained by a GGD random generator. A simple algorithm of constructing the Extended Zero Zone (EZZ) quantizer is proposed. Simulation results show that the EZZ quantizer yields a negligible loss in terms of coding efficiency compared to optimal scalar quantizers. Furthermore, we describe an adaptive version of the EZZ quantizer which works efficiently with low bitrate requirements for transmitting side information
On Sequences with Non-Learnable Subsequences
Venue: arXiv cs.AI 2008
Year: 2008

The remarkable results of Foster and Vohra was a starting point for a series of papers which show that any sequence of outcomes can be learned (with no prior knowledge) using some universal randomized forecasting algorithm and forecast-dependent checking rules. We show that for the class of all computationally efficient outcome-forecast-based checking rules, this property is violated. Moreover, we present a probabilistic algorithm generating with probability close to one a sequence with a subsequence which simultaneously miscalibrates all partially weakly computable randomized forecasting algorithms. %subsequences non-learnable by each randomized algorithm. According to the Dawid's prequential framework we consider partial recursive randomized algorithms.
The 1-fixed-endpoint Path Cover Problem is Polynomial on Interval Graph
Venue: arXiv cs.DS 2008
Year: 2008

We consider a variant of the path cover problem, namely, the $k$-fixed-endpoint path cover problem, or kPC for short, on interval graphs. Given a graph $G$ and a subset $\mathcal{T}$ of $k$ vertices of $V(G)$, a $k$-fixed-endpoint path cover of $G$ with respect to $\mathcal{T}$ is a set of vertex-disjoint paths $\mathcal{P}$ that covers the vertices of $G$ such that the $k$ vertices of $\mathcal{T}$ are all endpoints of the paths in $\mathcal{P}$. The kPC problem is to find a $k$-fixed-endpoint path cover of $G$ of minimum cardinality; note that, if $\mathcal{T}$ is empty the stated problem coincides with the classical path cover problem. In this paper, we study the 1-fixed-endpoint path cover problem on interval graphs, or 1PC for short, generalizing the 1HP problem which has been proved to be NP-complete even for small classes of graphs. Motivated by a work of Damaschke, where he left both 1HP and 2HP problems open for the class of interval graphs, we show that the 1PC problem can be solved in polynomial time on the class of interval graphs. The proposed algorithm is simple, runs in $O(n^2)$ time, requires linear space, and also enables us to solve the 1HP problem on interval graphs within the same time and space complexity.
Computationally Efficient Estimators for Dimension Reductions Using Stable Random Projections
Venue: arXiv cs.LG 2008
Year: 2008

The method of stable random projections is a tool for efficiently computing the $l_α$ distances using low memory, where $0<α\leq 2$ is a tuning parameter. The method boils down to a statistical estimation task and various estimators have been proposed, based on the geometric mean, the harmonic mean, and the fractional power etc. This study proposes the optimal quantile estimator, whose main operation is selecting, which is considerably less expensive than taking fractional power, the main operation in previous estimators. Our experiments report that the optimal quantile estimator is nearly one order of magnitude more computationally efficient than previous estimators. For large-scale learning tasks in which storing and computing pairwise distances is a serious bottleneck, this estimator should be desirable. In addition to its computational advantages, the optimal quantile estimator exhibits nice theoretical properties. It is more accurate than previous estimators when $α>1$. We derive its theoretical error bounds and establish the explicit (i.e., no hidden constants) sample complexity bound.
On Approximating the Lp Distances for p>2
Venue: arXiv cs.LG 2008
Year: 2008

Applications in machine learning and data mining require computing pairwise Lp distances in a data matrix A. For massive high-dimensional data, computing all pairwise distances of A can be infeasible. In fact, even storing A or all pairwise distances of A in the memory may be also infeasible. This paper proposes a simple method for p = 2, 4, 6, ... We first decompose the l_p (where p is even) distances into a sum of 2 marginal norms and p-1 ``inner products'' at different orders. Then we apply normal or sub-Gaussian random projections to approximate the resultant ``inner products,'' assuming that the marginal norms can be computed exactly by a linear scan. We propose two strategies for applying random projections. The basic projection strategy requires only one projection matrix but it is more difficult to analyze, while the alternative projection strategy requires p-1 projection matrices but its theoretical analysis is much easier. In terms of the accuracy, at least for p=4, the basic strategy is always more accurate than the alternative strategy if the data are non-negative, which is common in reality.
Signal Codes
Venue: arXiv cs.IT 2008
Year: 2008

Motivated by signal processing, we present a new class of channel codes, called signal codes, for continuous-alphabet channels. Signal codes are lattice codes whose encoding is done by convolving an integer information sequence with a fixed filter pattern. Decoding is based on the bidirectional sequential stack decoder, which can be implemented efficiently using the heap data structure. Error analysis and simulation results indicate that signal codes can achieve low error rate at approximately 1dB from channel capacity.
Termination of lambda-calculus with the extra Call-By-Value rule known as assoc
Venue: arXiv cs.LO 2008
Year: 2008

In this paper we prove that any lambda-term that is strongly normalising for beta-reduction is also strongly normalising for beta,assoc-reduction. assoc is a call-by-value rule that has been used in works by Moggi, Joachimsky, Espirito Santo and others. The result has often been justified with incomplete or incorrect proofs. Here we give one in full details.
Bounds on Codes Based on Graph Theory
Venue: arXiv cs.IT 2008
Year: 2008

Let $A_q(n,d)$ be the maximum order (maximum number of codewords) of a $q$-ary code of length $n$ and Hamming distance at least $d$. And let $A(n,d,w)$ that of a binary code of constant weight $w$. Building on results from algebraic graph theory and Erdős-ko-Rado like theorems in extremal combinatorics, we show how several known bounds on $A_q(n,d)$ and $A(n,d,w)$ can be easily obtained in a single framework. For instance, both the Hamming and Singleton bounds can derived as an application of a property relating the clique number and the independence number of vertex transitive graphs. Using the same techniques, we also derive some new bounds and present some additional applications.
Diversity Multiplexing Tradeoff of Asynchronous Cooperative Relay Networks
Venue: arXiv cs.IT 2008
Year: 2008

The assumption of nodes in a cooperative communication relay network operating in synchronous fashion is often unrealistic. In the present paper, we consider two different models of asynchronous operation in cooperative-diversity networks experiencing slow fading and examine the corresponding diversity-multiplexing tradeoffs (DMT). For both models, we propose protocols and distributed space-time codes that asymptotically achieve the transmit diversity bound for all multiplexing gains and for any number of relays.
Asymptotic Mean Time To Failure and Higher Moments for Large, Recursive Networks
Venue: arXiv cs.PF 2008
Year: 2008

This paper deals with asymptotic expressions of the Mean Time To Failure (MTTF) and higher moments for large, recursive, and non-repairable systems in the context of two-terminal reliability. Our aim is to extend the well-known results of the series and parallel cases. We first consider several exactly solvable configurations of identical components with exponential failure-time distribution functions to illustrate different (logarithmic or power-law) behaviors as the size of the system, indexed by an integer n, increases. The general case is then addressed: it provides a simple interpretation of the origin of the power-law exponent and an efficient asymptotic expression for the total reliability of large, recursive systems. Finally, we assess the influence of the non-exponential character of the component reliability on the n-dependence of the MTTF.
Belief decision support and reject for textured images characterization
Venue: arXiv cs.AI 2008
Year: 2008

The textured images' classification assumes to consider the images in terms of area with the same texture. In uncertain environment, it could be better to take an imprecise decision or to reject the area corresponding to an unlearning class. Moreover, on the areas that are the classification units, we can have more than one texture. These considerations allows us to develop a belief decision model permitting to reject an area as unlearning and to decide on unions and intersections of learning classes. The proposed approach finds all its justification in an application of seabed characterization from sonar images, which contributes to an illustration.
Knowledge bases over algebraic models. Some notes about informational equivalence
Venue: arXiv cs.LO 2008
Year: 2008

The recent advances in knowledge base research and the growing importance of effective knowledge management raised an important question of knowledge base equivalence verification. This problem has not been stated earlier, at least in a way that allows speaking about algorithms for verification of informational equivalence, because the informal definition of knowledge bases makes formal solution of this problem impossible. In this paper we provide an implementable formal algorithm for knowledge base equivalence verification based on the formal definition of knowledge base proposed by Plotkin B. and Plotkin T., and study some important properties of automorphic equivalence of models. We also describe the concept of equivalence and formulate the criterion for the equivalence of knowledge bases defined over finite models. Further we define multi-models and automorphic equivalence of models and multi-models, that is generalization of automorphic equivalence of algebras.
The Correspondence Analysis Platform for Uncovering Deep Structure in Data and Information
Venue: arXiv cs.AI 2008
Year: 2008

We study two aspects of information semantics: (i) the collection of all relationships, (ii) tracking and spotting anomaly and change. The first is implemented by endowing all relevant information spaces with a Euclidean metric in a common projected space. The second is modelled by an induced ultrametric. A very general way to achieve a Euclidean embedding of different information spaces based on cross-tabulation counts (and from other input data formats) is provided by Correspondence Analysis. From there, the induced ultrametric that we are particularly interested in takes a sequential - e.g. temporal - ordering of the data into account. We employ such a perspective to look at narrative, "the flow of thought and the flow of language" (Chafe). In application to policy decision making, we show how we can focus analysis in a small number of dimensions.
Measurement and Evaluation of ENUM Server Performance
Venue: arXiv cs.PF 2008
Year: 2008

ENUM is a DNS-based protocol standard for mapping E.164 telephone numbers to Internet Uniform Resource Identifiers (URIs). It places unique requirements on the existing DNS infrastructure, such as data scalability, query throughput, response time, and database update rates. This paper measures and evaluates the performance of existing name server implementation as ENUM servers. We compared PowerDNS (PDNS), BIND and Navitas. Results show that BIND is not suitable for ENUM due to its poor scaling property. Both PDNS and Navitas can serve ENUM. However, Navitas turns out to be highly optimized and clearly outperforms PDNS in all aspects we have tested. We also instrumented the PDNS server to identify its performance bottleneck and investigated ways to improve it.