OpenRaiser/Intern-Atlas huggingface dataset:
On the Theorem of Uniform Recovery of Random Sampling Matrices
Venue: arXiv cs.IT 2013
Year: 2013

We consider two theorems from the theory of compressive sensing. Mainly a theorem concerning uniform recovery of random sampling matrices, where the number of samples needed in order to recover an $s$-sparse signal from linear measurements (with high probability) is known to be $m\gtrsim s(\ln s)^3\ln N$. We present new and improved constants together with what we consider to be a more explicit proof. A proof that also allows for a slightly larger class of $m\times N$-matrices, by considering what we call \emph{low entropy}. We also present an improved condition on the so-called restricted isometry constants, $δ_s$, ensuring sparse recovery via $\ell^1$-minimization. We show that $δ_{2s}<4/\sqrt{41}$ is sufficient and that this can be improved further to almost allow for a sufficient condition of the type $δ_{2s}<2/3$.
Stabilizing Nonuniformly Quantized Compressed Sensing with Scalar Companders
Venue: arXiv cs.IT 2013
Year: 2013

This paper studies the problem of reconstructing sparse or compressible signals from compressed sensing measurements that have undergone nonuniform quantization. Previous approaches to this Quantized Compressed Sensing (QCS) problem based on Gaussian models (bounded l2-norm) for the quantization distortion yield results that, while often acceptable, may not be fully consistent: re-measurement and quantization of the reconstructed signal do not necessarily match the initial observations. Quantization distortion instead more closely resembles heteroscedastic uniform noise, with variance depending on the observed quantization bin. Generalizing our previous work on uniform quantization, we show that for nonuniform quantizers described by the "compander" formalism, quantization distortion may be better characterized as having bounded weighted lp-norm (p >= 2), for a particular weighting. We develop a new reconstruction approach, termed Generalized Basis Pursuit DeNoise (GBPDN), which minimizes the sparsity of the reconstructed signal under this weighted lp-norm fidelity constraint. We prove that for B bits per measurement and under the oversampled QCS scenario (when the number of measurements is large compared to the signal sparsity) if the sensing matrix satisfies a proposed generalized Restricted Isometry Property, then, GBPDN provides a reconstruction error of sparse signals which decreases like O(2^{-B}/\sqrt{p+1}): a reduction by a factor \sqrt{p+1} relative to that produced by using the l2-norm. Besides the QCS scenario, we also show that GBPDN applies straightforwardly to the related case of CS measurements corrupted by heteroscedastic Generalized Gaussian noise with provable reconstruction error reduction. Finally, we describe an efficient numerical procedure for computing GBPDN via a primal-dual convex optimization scheme, and demonstrate its effectiveness through simulations.
Data Structures on Event Graphs
Venue: arXiv cs.DS 2013
Year: 2013

We investigate the behavior of data structures when the input and operations are generated by an event graph. This model is inspired by Markov chains. We are given a fixed graph G, whose nodes are annotated with operations of the type insert, delete and query. The algorithm responds to the requests as it encounters them during a (random or adversarial) walk in G. We study the limit behavior of such a walk and give an efficient algorithm for recognizing which structures can be generated. We also give a near-optimal algorithm for successor searching if the event graph is a cycle and the walk is adversarial. For a random walk, the algorithm becomes optimal.
On Complexity of Flooding Games on Graphs with Interval Representations
Venue: arXiv cs.DM 2013
Year: 2013

The flooding games, which are called Flood-It, Mad Virus, or HoneyBee, are a kind of coloring games and they have been becoming popular online. In these games, each player colors one specified cell in his/her turn, and all connected neighbor cells of the same color are also colored by the color. This flooding or coloring spreads on the same color cells. It is natural to consider these new coloring games on more general boards, or general graphs. Recently, computational complexities of the variants of the flooding games on several graph classes have been studied. In this paper, we investigate the flooding games on some graph classes characterized by interval representations. Our results state that the number of colors is a key parameter to determine the computational complexity of the flooding games. When the number of colors is a fixed constant, these games can be solved in polynomial time on an interval graph. On the other hand, if the number of colors is not bounded, the flooding game is NP-complete on a proper interval graph. We also state similar results for split graphs.
A Low-Depth Monotone Function that is not an Approximate Junta
Venue: arXiv cs.DM 2013
Year: 2013

We provide an example of a monotone Boolean function on the hypercube given by a low depth decision tree that is not well approximated by any k-junta for small k.
On Multilabel Classification and Ranking with Partial Feedback
Venue: arXiv cs.LG 2013
Year: 2013

We present a novel multilabel/ranking algorithm working in partial information settings. The algorithm is based on 2nd-order descent methods, and relies on upper-confidence bounds to trade-off exploration and exploitation. We analyze this algorithm in a partial adversarial setting, where covariates can be adversarial, but multilabel probabilities are ruled by (generalized) linear models. We show O(T^{1/2} log T) regret bounds, which improve in several ways on the existing results. We test the effectiveness of our upper-confidence scheme by contrasting against full-information baselines on real-world multilabel datasets, often obtaining comparable performance.
Extending Partial Representations of Subclasses of Chordal Graphs
Venue: arXiv cs.CC 2013
Year: 2013

Chordal graphs are intersection graphs of subtrees of a tree T. We investigate the complexity of the partial representation extension problem for chordal graphs. A partial representation specifies a tree T' and some pre-drawn subtrees of T'. It asks whether it is possible to construct a representation inside a modified tree T which extends the partial representation (i.e, keeps the pre-drawn subtrees unchanged). We consider four modifications of T' and get vastly different problems. In some cases, it is interesting to consider the complexity even if just T' is given and no subtree is pre-drawn. Also, we consider three well-known subclasses of chordal graphs: Proper interval graphs, interval graphs and path graphs. We give an almost complete complexity characterization. We further study the parametrized complexity of the problems when parametrized by the number of pre-drawn subtrees, the number of components and the size of the tree T'. We describe an interesting relation with integer partition problems. The problem Partition is used for all NP-completeness reductions. The extension of interval graphs when the space in T' is limited is "equivalent" to the BinPacking problem.
Algorithms for Approximate Minimization of the Difference Between Submodular Functions, with Applications
Venue: arXiv cs.DS 2013
Year: 2013

We extend the work of Narasimhan and Bilmes [30] for minimizing set functions representable as a difference between submodular functions. Similar to [30], our new algorithms are guaranteed to monotonically reduce the objective function at every step. We empirically and theoretically show that the per-iteration cost of our algorithms is much less than [30], and our algorithms can be used to efficiently minimize a difference between submodular functions under various combinatorial constraints, a problem not previously addressed. We provide computational bounds and a hardness result on the mul- tiplicative inapproximability of minimizing the difference between submodular functions. We show, however, that it is possible to give worst-case additive bounds by providing a polynomial time computable lower-bound on the minima. Finally we show how a number of machine learning problems can be modeled as minimizing the difference between submodular functions. We experimentally show the validity of our algorithms by testing them on the problem of feature selection with submodular cost features.
Playing Mastermind with Many Colors
Venue: arXiv cs.DS 2013
Year: 2013

We analyze the general version of the classic guessing game Mastermind with $n$ positions and $k$ colors. Since the case $k \le n^{1-\varepsilon}$, $\varepsilon>0$ a constant, is well understood, we concentrate on larger numbers of colors. For the most prominent case $k = n$, our results imply that Codebreaker can find the secret code with $O(n \log \log n)$ guesses. This bound is valid also when only black answer-pegs are used. It improves the $O(n \log n)$ bound first proven by Chvátal (Combinatorica 3 (1983), 325--329). We also show that if both black and white answer-pegs are used, then the $O(n \log\log n)$ bound holds for up to $n^2 \log\log n$ colors. These bounds are almost tight as the known lower bound of $Ω(n)$ shows. Unlike for $k \le n^{1-\varepsilon}$, simply guessing at random until the secret code is determined is not sufficient. In fact, we show that an optimal non-adaptive strategy (deterministic or randomized) needs $Θ(n \log n)$ guesses.
Signal Estimation with Additive Error Metrics in Compressed Sensing
Venue: arXiv cs.IT 2013
Year: 2013

Compressed sensing typically deals with the estimation of a system input from its noise-corrupted linear measurements, where the number of measurements is smaller than the number of input components. The performance of the estimation process is usually quantified by some standard error metric such as squared error or support set error. In this correspondence, we consider a noisy compressed sensing problem with any arbitrary error metric. We propose a simple, fast, and highly general algorithm that estimates the original signal by minimizing the error metric defined by the user. We verify that our algorithm is optimal owing to the decoupling principle, and we describe a general method to compute the fundamental information-theoretic performance limit for any error metric. We provide two example metrics --- minimum mean absolute error and minimum mean support error --- and give the theoretical performance limits for these two cases. Experimental results show that our algorithm outperforms methods such as relaxed belief propagation (relaxed BP) and compressive sampling matching pursuit (CoSaMP), and reaches the suggested theoretical limits for our two example metrics.
Second-Order Slepian-Wolf Coding Theorems for Non-Mixed and Mixed Sources
Venue: arXiv cs.IT 2013
Year: 2013

The second-order achievable rate region in Slepian-Wolf source coding systems is investigated. The concept of second-order achievable rates, which enables us to make a finer evaluation of achievable rates, has already been introduced and analyzed for general sources in the single-user source coding problem. Analogously, in this paper, we first define the second-order achievable rate region for the Slepian-Wolf coding system to establish the source coding theorem in the second- order sense. The Slepian-Wolf coding problem for correlated sources is one of typical problems in the multi-terminal information theory. In particular, Miyake and Kanaya, and Han have established the first-order source coding theorems for general correlated sources. On the other hand, in general, the second-order achievable rate problem for the Slepian-Wolf coding system with general sources remains still open up to present. In this paper we present the analysis concerning the second- order achievable rates for general sources which are based on the information spectrum methods developed by Han and Verdu. Moreover, we establish the explicit second-order achievable rate region for i.i.d. correlated sources with countably infinite alphabets and mixed correlated sources, respectively, using the relevant asymptotic normality.
Information-bit error rate and false positives in an MDS code
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, a refinement of the weight distribution in an MDS code is computed. Concretely, the number of codewords with a fixed amount of nonzero bits in both information and redundancy parts is obtained. This refinement improves the theoretical approximation of the information-bit and -symbol error rate, in terms of the channel bit-error rate, in a block transmission through a discrete memoryless channel. Since a bounded distance reproducing encoder is assumed, the computation of the here-called false positive (a decoding failure with no information-symbol error) is provided. As a consequence, a new performance analysis of an MDS code is proposed.
Sparse Recovery with Graph Constraints
Venue: arXiv cs.IT 2013
Year: 2013

Sparse recovery can recover sparse signals from a set of underdetermined linear measurements. Motivated by the need to monitor large-scale networks from a limited number of measurements, this paper addresses the problem of recovering sparse signals in the presence of network topological constraints. Unlike conventional sparse recovery where a measurement can contain any subset of the unknown variables, we use a graph to characterize the topological constraints and allow an additive measurement over nodes (unknown variables) only if they induce a connected subgraph. We provide explicit measurement constructions for several special graphs, and the number of measurements by our construction is less than that needed by existing random constructions. Moreover, our construction for a line network is provably optimal in the sense that it requires the minimum number of measurements. A measurement construction algorithm for general graphs is also proposed and evaluated. For any given graph $G$ with $n$ nodes, we derive bounds of the minimum number of measurements needed to recover any $k$-sparse vector over $G$ ($M^G_{k,n}$). Using the Erdős-Rényi random graph as an example, we characterize the dependence of $M^G_{k,n}$ on the graph structure.
Compressed sensing with sparse, structured matrices
Venue: arXiv cs.IT 2013
Year: 2013

In the context of the compressed sensing problem, we propose a new ensemble of sparse random matrices which allow one (i) to acquire and compress a ρ0-sparse signal of length N in a time linear in N and (ii) to perfectly recover the original signal, compressed at a rate α, by using a message passing algorithm (Expectation Maximization Belief Propagation) that runs in a time linear in N. In the large N limit, the scheme proposed here closely approaches the theoretical bound ρ0 = α, and so it is both optimal and efficient (linear time complexity). More generally, we show that several ensembles of dense random matrices can be converted into ensembles of sparse random matrices, having the same thresholds, but much lower computational complexity.
Fundamental Limits of Communications in Interference Networks-Part II: Information Flow in Degraded Networks
Venue: arXiv cs.IT 2013
Year: 2013

In this second part of our multi-part papers, the information flow in degraded interference networks is studied. A full characterization of the sum-rate capacity for the degraded networks with any possible configuration is established. It is shown that a successive decoding scheme is sum-rate optimal for these networks. Also, it is proved that the transmission of only a certain subset of messages is sufficient to achieve the sum-rate capacity in such networks. Algorithms are presented to determine this subset of messages explicitly. According to these algorithms, the optimal strategy to achieve the sum-rate capacity in degraded networks is that the transmitters try to send information for the stronger receivers and, if possible, avoid sending the messages with respect to the weaker receivers. The algorithms are easily understood using our graphical illustrations for the achievability schemes based on directed graphs. The sum-rate expression for the degraded networks is then used to derive a unified outer bound on the sum-rate capacity of arbitrary non-degraded networks. Several variations of the degraded networks are identified for which the derived outer bound is sum-rate optimal. Specifically, noisy interference regimes are derived for certain classes of multi-user/multi-message interference networks. Also, for the first time, network scenarios are identified where the incorporation of both successive decoding and treating interference as noise achieves their sum-rate capacity. Finally, by taking insight from our results for degraded networks, we establish a unified outer bound on the entire capacity region of the general interference networks. These outer bounds for a broad range of network scenarios are tighter than the existing cut-set bound.
How Much Rate Splitting Is Required for a Random Coding Scheme? A new Achievable Rate Region for the Broadcast Channel with Cognitive Relays
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, it is shown that for any given single-hop communication network with two receivers, splitting messages into more than two sub-messages in a random coding scheme is redundant. To this end, the Broadcast Channel with Cognitive Relays (BCCR) is considered. A novel achievability scheme is designed for this network. Our achievability design is derived by a systematic combination of the best known achievability schemes for the basic building blocks included in the network: the Han-Kobayashi scheme for the two-user interference channel and the Marton coding scheme for the broadcast channel. Meanwhile, in our scheme each private message is split into only two sub-messages which is identically exploited also in the Han-Kobayashi scheme. It is shown that the resultant achievable rate region includes previous results as well. More importantly, the procedure of the achievability design is described by graphical illustrations based on directed graphs. Then, it is argued that by extending the proposed scheme on the MACCM plan of messages, one can derive similar achievability schemes for any other single-hop communication network.
Real-Time Peer-to-Peer Streaming Over Multiple Random Hamiltonian Cycles
Venue: arXiv cs.NI 2013
Year: 2013

We are motivated by the problem of designing a simple distributed algorithm for Peer-to-Peer streaming applications that can achieve high throughput and low delay, while allowing the neighbor set maintained by each peer to be small. While previous works have mostly used tree structures, our algorithm constructs multiple random directed Hamiltonian cycles and disseminates content over the superposed graph of the cycles. We show that it is possible to achieve the maximum streaming capacity even when each peer only transmits to and receives from Theta(1) neighbors. Further, we show that the proposed algorithm achieves the streaming delay of Theta(log N) when the streaming rate is less than (1-1/K) of the maximum capacity for any fixed integer K>1, where N denotes the number of peers in the network. The key theoretical contribution is to characterize the distance between peers in a graph formed by the superposition of directed random Hamiltonian cycles, in which edges from one of the cycles may be dropped at random. We use Doob martingales and graph expansion ideas to characterize this distance as a function of N, with high probability.
Probabilistic Event Calculus for Event Recognition
Venue: arXiv cs.AI 2013
Year: 2013

Symbolic event recognition systems have been successfully applied to a variety of application domains, extracting useful information in the form of events, allowing experts or other systems to monitor and respond when significant events are recognised. In a typical event recognition application, however, these systems often have to deal with a significant amount of uncertainty. In this paper, we address the issue of uncertainty in logic-based event recognition by extending the Event Calculus with probabilistic reasoning. Markov Logic Networks are a natural candidate for our logic-based formalism. However, the temporal semantics of the Event Calculus introduce a number of challenges for the proposed model. We show how and under what assumptions we can overcome these problems. Additionally, we study how probabilistic modelling changes the behaviour of the formalism, affecting its key property, the inertia of fluents. Furthermore, we demonstrate the advantages of the probabilistic Event Calculus through examples and experiments in the domain of activity recognition, using a publicly available dataset for video surveillance.
Hierarchical Approach for Total Variation Digital Image Inpainting
Venue: arXiv cs.CV 2013
Year: 2013

The art of recovering an image from damage in an undetectable form is known as inpainting. The manual work of inpainting is most often a very time consuming process. Due to digitalization of this technique, it is automatic and faster. In this paper, after the user selects the regions to be reconstructed, the algorithm automatically reconstruct the lost regions with the help of the information surrounding them. The existing methods perform very well when the region to be reconstructed is very small, but fails in proper reconstruction as the area increases. This paper describes a Hierarchical method by which the area to be inpainted is reduced in multiple levels and Total Variation(TV) method is used to inpaint in each level. This algorithm gives better performance when compared with other existing algorithms such as nearest neighbor interpolation, Inpainting through Blurring and Sobolev Inpainting.
MARFCAT: Transitioning to Binary and Larger Data Sets of SATE IV
Venue: arXiv cs.CR 2013
Year: 2013

We present a second iteration of a machine learning approach to static code analysis and fingerprinting for weaknesses related to security, software engineering, and others using the open-source MARF framework and the MARFCAT application based on it for the NIST's SATE IV static analysis tool exposition workshop's data sets that include additional test cases, including new large synthetic cases. To aid detection of weak or vulnerable code, including source or binary on different platforms the machine learning approach proved to be fast and accurate to for such tasks where other tools are either much slower or have much smaller recall of known vulnerabilities. We use signal and NLP processing techniques in our approach to accomplish the identification and classification tasks. MARFCAT's design from the beginning in 2010 made is independent of the language being analyzed, source code, bytecode, or binary. In this follow up work with explore some preliminary results in this area. We evaluated also additional algorithms that were used to process the data.