OpenRaiser/Intern-Atlas huggingface dataset:
The Phase Transition of Matrix Recovery from Gaussian Measurements Matches the Minimax MSE of Matrix Denoising
Venue: arXiv cs.IT 2013
Year: 2013

Let $X_0$ be an unknown $M$ by $N$ matrix. In matrix recovery, one takes $n < MN$ linear measurements $y_1,..., y_n$ of $X_0$, where $y_i = \Tr(a_i^T X_0)$ and each $a_i$ is a $M$ by $N$ matrix. For measurement matrices with Gaussian i.i.d entries, it known that if $X_0$ is of low rank, it is recoverable from just a few measurements. A popular approach for matrix recovery is Nuclear Norm Minimization (NNM). Empirical work reveals a \emph{phase transition} curve, stated in terms of the undersampling fraction $δ(n,M,N) = n/(MN)$, rank fraction $ρ=r/N$ and aspect ratio $β=M/N$. Specifically, a curve $δ^* = δ^*(ρ;β)$ exists such that, if $δ> δ^*(ρ;β)$, NNM typically succeeds, while if $δ< δ^*(ρ;β)$, it typically fails. An apparently quite different problem is matrix denoising in Gaussian noise, where an unknown $M$ by $N$ matrix $X_0$ is to be estimated based on direct noisy measurements $Y = X_0 + Z$, where the matrix $Z$ has iid Gaussian entries. It has been empirically observed that, if $X_0$ has low rank, it may be recovered quite accurately from the noisy measurement $Y$. A popular matrix denoising scheme solves the unconstrained optimization problem $\text{min} \| Y - X \|_F^2/2 + λ\|X\|_* $. When optimally tuned, this scheme achieves the asymptotic minimax MSE $\cM(ρ) = \lim_{N \goto \infty} \inf_λ\sup_{\rank(X) \leq ρ\cdot N} MSE(X,\hat{X}_λ)$. We report extensive experiments showing that the phase transition $δ^*(ρ)$ in the first problem coincides with the minimax risk curve $\cM(ρ)$ in the second problem, for {\em any} rank fraction $0 < ρ< 1$.
Adaptive Space-Time Beamforming in Radar Systems
Venue: arXiv cs.IT 2013
Year: 2013

The goal of this chapter is to review the recent work and advances in the area of space-time beamforming algorithms and their application to radar systems. These systems include phased-array \cite{melvin} and multi-input multi-output (MIMO) radar systems \cite{haimo_08}, mono-static and bi-static radar systems and other configurations \cite{melvin}. Furthermore, this chapter also describes in detail some of the most successful space-time beamforming algorithms that exploit low-rank and sparsity properties as well as the use of prior-knowledge to improve the performance of STAP algorithms in radar systems.
Signature Based Detection of User Events for Post-Mortem Forensic Analysis
Venue: arXiv cs.CR 2013
Year: 2013

This paper introduces a novel approach to user event reconstruction by showing the practicality of generating and implementing signature-based analysis methods to reconstruct high-level user actions from a collection of low-level traces found during a post-mortem forensic analysis of a system. Traditional forensic analysis and the inferences an investigator normally makes when given digital evidence, are examined. It is then demonstrated that this natural process of inferring high-level events from low-level traces may be encoded using signature-matching techniques. Simple signatures using the defined method are created and applied for three popular Windows-based programs as a proof of concept.
Coloring Hypergraphs Induced by Dynamic Point Sets and Bottomless Rectangles
Venue: arXiv cs.CG 2013
Year: 2013

We consider a coloring problem on dynamic, one-dimensional point sets: points appearing and disappearing on a line at given times. We wish to color them with k colors so that at any time, any sequence of p(k) consecutive points, for some function p, contains at least one point of each color. We prove that no such function p(k) exists in general. However, in the restricted case in which points appear gradually, but never disappear, we give a coloring algorithm guaranteeing the property at any time with p(k)=3k-2. This can be interpreted as coloring point sets in R^2 with k colors such that any bottomless rectangle containing at least 3k-2 points contains at least one point of each color. Here a bottomless rectangle is an axis-aligned rectangle whose bottom edge is below the lowest point of the set. For this problem, we also prove a lower bound p(k)>ck, where c>1.67. Hence for every k there exists a point set, every k-coloring of which is such that there exists a bottomless rectangle containing ck points and missing at least one of the k colors. Chen et al. (2009) proved that no such function $p(k)$ exists in the case of general axis-aligned rectangles. Our result also complements recent results from Keszegh and Palvolgyi on cover-decomposability of octants (2011, 2012).
Extracting useful rules through improved decision tree induction using information entropy
Venue: arXiv cs.LG 2013
Year: 2013

Classification is widely used technique in the data mining domain, where scalability and efficiency are the immediate problems in classification algorithms for large databases. We suggest improvements to the existing C4.5 decision tree algorithm. In this paper attribute oriented induction (AOI) and relevance analysis are incorporated with concept hierarchys knowledge and HeightBalancePriority algorithm for construction of decision tree along with Multi level mining. The assignment of priorities to attributes is done by evaluating information entropy, at different levels of abstraction for building decision tree using HeightBalancePriority algorithm. Modified DMQL queries are used to understand and explore the shortcomings of the decision trees generated by C4.5 classifier for education dataset and the results are compared with the proposed approach.
Optimal Forgery and Suppression of Ratings for Privacy Enhancement in Recommendation Systems
Venue: arXiv cs.IT 2013
Year: 2013

Recommendation systems are information-filtering systems that tailor information to users on the basis of knowledge about their preferences. The ability of these systems to profile users is what enables such intelligent functionality, but at the same time, it is the source of serious privacy concerns. In this paper we investigate a privacy-enhancing technology that aims at hindering an attacker in its efforts to accurately profile users based on the items they rate. Our approach capitalizes on the combination of two perturbative mechanisms---the forgery and the suppression of ratings. While this technique enhances user privacy to a certain extent, it inevitably comes at the cost of a loss in data utility, namely a degradation of the recommendation's accuracy. In short, it poses a trade-off between privacy and utility. The theoretical analysis of said trade-off is the object of this work. We measure privacy as the Kullback-Leibler divergence between the user's and the population's item distributions, and quantify utility as the proportion of ratings users consent to forge and eliminate. Equipped with these quantitative measures, we find a closed-form solution to the problem of optimal forgery and suppression of ratings, and characterize the trade-off among privacy, forgery rate and suppression rate. Experimental results on a popular recommendation system show how our approach may contribute to privacy enhancement.
Which Boolean Functions are Most Informative?
Venue: arXiv cs.IT 2013
Year: 2013

We introduce a simply stated conjecture regarding the maximum mutual information a Boolean function can reveal about noisy inputs. Specifically, let $X^n$ be i.i.d. Bernoulli(1/2), and let $Y^n$ be the result of passing $X^n$ through a memoryless binary symmetric channel with crossover probability $α$. For any Boolean function $b:\{0,1\}^n\rightarrow \{0,1\}$, we conjecture that $I(b(X^n);Y^n)\leq 1-H(α)$. While the conjecture remains open, we provide substantial evidence supporting its validity.
Online Regret Bounds for Undiscounted Continuous Reinforcement Learning
Venue: arXiv cs.LG 2013
Year: 2013

We derive sublinear regret bounds for undiscounted reinforcement learning in continuous state space. The proposed algorithm combines state aggregation with the use of upper confidence bounds for implementing optimism in the face of uncertainty. Beside the existence of an optimal policy which satisfies the Poisson equation, the only assumptions made are Holder continuity of rewards and transition probabilities.
How to choose a PIN - assessment of dictionary methods
Venue: arXiv cs.CR 2013
Year: 2013

Personal Identification Numbers (PINs) are commonly used as an authentication mechanism. An important security requirement is that PINs should be hard to guess for an attacker. On the other hand, remembering several random PINs can be difficult task for an individual. We evaluate several dictionary-based methods of choosing a PIN. We experimentally show that these methods are far from ideal with respect to expected covering of the PIN space and the entropy of PINs. We also discuss two methods for constructing easy to memorize PIN words for randomly chosen PINs.
Coherence and sufficient sampling densities for reconstruction in compressed sensing
Venue: arXiv cs.LG 2013
Year: 2013

We give a new, very general, formulation of the compressed sensing problem in terms of coordinate projections of an analytic variety, and derive sufficient sampling rates for signal reconstruction. Our bounds are linear in the coherence of the signal space, a geometric parameter independent of the specific signal and measurement, and logarithmic in the ambient dimension where the signal is presented. We exemplify our approach by deriving sufficient sampling densities for low-rank matrix completion and distance matrix completion which are independent of the true matrix.
Minimum length path decompositions
Venue: arXiv cs.DS 2013
Year: 2013

We consider a bi-criteria generalization of the pathwidth problem, where, for given integers $k,l$ and a graph $G$, we ask whether there exists a path decomposition $\cP$ of $G$ such that the width of $\cP$ is at most $k$ and the number of bags in $\cP$, i.e., the \emph{length} of $\cP$, is at most $l$. We provide a complete complexity classification of the problem in terms of $k$ and $l$ for general graphs. Contrary to the original pathwidth problem, which is fixed-parameter tractable with respect to $k$, we prove that the generalized problem is NP-complete for any fixed $k\geq 4$, and is also NP-complete for any fixed $l\geq 2$. On the other hand, we give a polynomial-time algorithm that, for any (possibly disconnected) graph $G$ and integers $k\leq 3$ and $l>0$, constructs a path decomposition of width at most $k$ and length at most $l$, if any exists. As a by-product, we obtain an almost complete classification of the problem in terms of $k$ and $l$ for connected graphs. Namely, the problem is NP-complete for any fixed $k\geq 5$ and it is polynomial-time for any $k\leq 3$. This leaves open the case $k=4$ for connected graphs.
Linear and Geometric Mixtures - Analysis
Venue: arXiv cs.IT 2013
Year: 2013

Linear and geometric mixtures are two methods to combine arbitrary models in data compression. Geometric mixtures generalize the empirically well-performing PAQ7 mixture. Both mixture schemes rely on weight vectors, which heavily determine their performance. Typically weight vectors are identified via Online Gradient Descent. In this work we show that one can obtain strong code length bounds for such a weight estimation scheme. These bounds hold for arbitrary input sequences. For this purpose we introduce the class of nice mixtures and analyze how Online Gradient Descent with a fixed step size combined with a nice mixture performs. These results translate to linear and geometric mixtures, which are nice, as we show. The results hold for PAQ7 mixtures as well, thus we provide the first theoretical analysis of PAQ7.
Lingering Issues in Distributed Scheduling
Venue: arXiv cs.NI 2013
Year: 2013

Recent advances have resulted in queue-based algorithms for medium access control which operate in a distributed fashion, and yet achieve the optimal throughput performance of centralized scheduling algorithms. However, fundamental performance bounds reveal that the "cautious" activation rules involved in establishing throughput optimality tend to produce extremely large delays, typically growing exponentially in 1/(1-r), with r the load of the system, in contrast to the usual linear growth. Motivated by that issue, we explore to what extent more "aggressive" schemes can improve the delay performance. Our main finding is that aggressive activation rules induce a lingering effect, where individual nodes retain possession of a shared resource for excessive lengths of time even while a majority of other nodes idle. Using central limit theorem type arguments, we prove that the idleness induced by the lingering effect may cause the delays to grow with 1/(1-r) at a quadratic rate. To the best of our knowledge, these are the first mathematical results illuminating the lingering effect and quantifying the performance impact. In addition extensive simulation experiments are conducted to illustrate and validate the various analytical results.
Equivalence of Two Proof Techniques for Non-Shannon-type Inequalities
Venue: arXiv cs.IT 2013
Year: 2013

We compare two different techniques for proving non-Shannon-type information inequalities. The first one is the original Zhang-Yeung's method, commonly referred to as the copy/pasting lemma/trick. The copy lemma was used to derive the first conditional and unconditional non-Shannon-type inequalities. The second technique first appeared in Makarychev et al paper [7] and is based on a coding lemma from Ahlswede and Körner works. We first emphasize the importance of balanced inequalities and provide a simpler proof of a theorem of Chan's for the case of Shannon-type inequalities. We compare the power of various proof systems based on a single technique.
Viral spread with or without emotions in online community
Venue: arXiv cs.SI 2013
Year: 2013

Diffusion of information and viral content, social contagion and influence are still topics of broad evaluation. We have studied the information epidemic in a social networking platform in order compare different campaign setups. The goal of this work is to present the new knowledge obtained from studying two artificial (experimental) and one natural (where people act emotionally) viral spread that took place in a closed virtual world. We propose an approach to modeling the behavior of online community exposed on external impulses as an epidemic process. The presented results base on online multilayer system observation, and show characteristic difference between setups, moreover, some important aspects of branching processes are presented. We run experiments, where we introduced viral to system and agents were able to propagate it. There were two modes of experiment: with or without award. Dynamic of spreading both of virals were described by epidemiological model and diffusion. Results of experiments were compared with real propagation process - spontaneous organization against ACTA. During general-national protest against new antypiracy multinational agreement - ACTA, criticized for its adverse effect on e.g. freedom of expression and privacy of communication, members of chosen community could send a viral such as Stop-ACTA transparent. In this scenario, we are able to capture behavior of society, when real emotions play a role, and compare results with artificiality conditioned experiments. Moreover, we could measure effect of emotions in viral propagation. As theory explaining the role of emotions in spreading behaviour as an factor of message targeting and individuals spread emotional-oriented content in a more carefully and more influential way, the experiments show that probabilities of secondary infections are four times bigger if emotions play a role.
Exploiting the Past to Reduce Delay in CSMA Scheduling: A High-order Markov Chain Approach
Venue: arXiv cs.NI 2013
Year: 2013

Recently several CSMA algorithms based on the Glauber dynamics model have been proposed for multihop wireless scheduling, as viable solutions to achieve the throughput optimality, yet are simple to implement. However, their delay performances still remain unsatisfactory, mainly due to the nature of the underlying Markov chains that imposes a fundamental constraint on how the link state can evolve over time. In this paper, we propose a new approach toward better queueing and delay performance, based on our observation that the algorithm needs not be Markovian, as long as it can be implemented in a distributed manner, achieve the same throughput optimality, while offering far better delay performance for general network topologies. Our approach hinges upon utilizing past state information observed by local link and then constructing a high-order Markov chain for the evolution of the feasible link schedules. We show in theory and simulation that our proposed algorithm, named delayed CSMA, adds virtually no additional overhead onto the existing CSMA-based algorithms, achieves the throughput optimality under the usual choice of link weight as a function of local queue length, and also provides much better delay performance by effectively `de-correlating' the link state process (thus removing link starvation) under any arbitrary network topology. From our extensive simulations we observe that the delay under our algorithm can be often reduced by a factor of 20 over a wide range of scenarios, compared to the standard Glauber-dynamics-based CSMA algorithm.
Constraint-based reachability
Venue: arXiv cs.LO 2013
Year: 2013

Iterative imperative programs can be considered as infinite-state systems computing over possibly unbounded domains. Studying reachability in these systems is challenging as it requires to deal with an infinite number of states with standard backward or forward exploration strategies. An approach that we call Constraint-based reachability, is proposed to address reachability problems by exploring program states using a constraint model of the whole program. The keypoint of the approach is to interpret imperative constructions such as conditionals, loops, array and memory manipulations with the fundamental notion of constraint over a computational domain. By combining constraint filtering and abstraction techniques, Constraint-based reachability is able to solve reachability problems which are usually outside the scope of backward or forward exploration strategies. This paper proposes an interpretation of classical filtering consistencies used in Constraint Programming as abstract domain computations, and shows how this approach can be used to produce a constraint solver that efficiently generates solutions for reachability problems that are unsolvable by other approaches.
CORE: Augmenting Regenerating-Coding-Based Recovery for Single and Concurrent Failures in Distributed Storage Systems
Venue: arXiv cs.DC 2013
Year: 2013

Data availability is critical in distributed storage systems, especially when node failures are prevalent in real life. A key requirement is to minimize the amount of data transferred among nodes when recovering the lost or unavailable data of failed nodes. This paper explores recovery solutions based on regenerating codes, which are shown to provide fault-tolerant storage and minimum recovery bandwidth. Existing optimal regenerating codes are designed for single node failures. We build a system called CORE, which augments existing optimal regenerating codes to support a general number of failures including single and concurrent failures. We theoretically show that CORE achieves the minimum possible recovery bandwidth for most cases. We implement CORE and evaluate our prototype atop a Hadoop HDFS cluster testbed with up to 20 storage nodes. We demonstrate that our CORE prototype conforms to our theoretical findings and achieves recovery bandwidth saving when compared to the conventional recovery approach based on erasure codes.
Recoloring bounded treewidth graphs
Venue: arXiv cs.DM 2013
Year: 2013

Let $k$ be an integer. Two vertex $k$-colorings of a graph are \emph{adjacent} if they differ on exactly one vertex. A graph is \emph{$k$-mixing} if any proper $k$-coloring can be transformed into any other through a sequence of adjacent proper $k$-colorings. Any graph is $(tw+2)$-mixing, where $tw$ is the treewidth of the graph (Cereceda 2006). We prove that the shortest sequence between any two $(tw+2)$-colorings is at most quadratic, a problem left open in Bonamy et al. (2012). Jerrum proved that any graph is $k$-mixing if $k$ is at least the maximum degree plus two. We improve Jerrum's bound using the grundy number, which is the worst number of colors in a greedy coloring.
Entailment in Probability of Thresholded Generalizations
Venue: arXiv cs.AI 2013
Year: 2013

A nonmonotonic logic of thresholded generalizations is presented. Given propositions A and B from a language L and a positive integer k, the thresholded generalization A=>B{k} means that the conditional probability P(B|A) falls short of one by no more than c*d^k. A two-level probability structure is defined. At the lower level, a model is defined to be a probability function on L. At the upper level, there is a probability distribution over models. A definition is given of what it means for a collection of thresholded generalizations to entail another thresholded generalization. This nonmonotonic entailment relation, called "entailment in probability", has the feature that its conclusions are "probabilistically trustworthy" meaning that, given true premises, it is improbable that an entailed conclusion would be false. A procedure is presented for ascertaining whether any given collection of premises entails any given conclusion. It is shown that entailment in probability is closely related to Goldszmidt and Pearl's System-Z^+, thereby demonstrating that the conclusions of System-Z^+ are probabilistically trustworthy.
Object Recognition with Imperfect Perception and Redundant Description
Venue: arXiv cs.CV 2013
Year: 2013

This paper deals with a scene recognition system in a robotics contex. The general problem is to match images with <I>a priori</I> descriptions. A typical mission would consist in identifying an object in an installation with a vision system situated at the end of a manipulator and with a human operator provided description, formulated in a pseudo-natural language, and possibly redundant. The originality of this work comes from the nature of the description, from the special attention given to the management of imprecision and uncertainty in the interpretation process and from the way to assess the description redundancy so as to reinforce the overall matching likelihood.
Approximations for Decision Making in the Dempster-Shafer Theory of Evidence
Venue: arXiv cs.AI 2013
Year: 2013

The computational complexity of reasoning within the Dempster-Shafer theory of evidence is one of the main points of criticism this formalism has to face. To overcome this difficulty various approximation algorithms have been suggested that aim at reducing the number of focal elements in the belief functions involved. Besides introducing a new algorithm using this method, this paper describes an empirical study that examines the appropriateness of these approximation procedures in decision making situations. It presents the empirical findings and discusses the various tradeoffs that have to be taken into account when actually applying one of these methods.