OpenRaiser/Intern-Atlas huggingface dataset:
Resolution Enhancement of Range Images via Color-Image Segmentation
Venue: arXiv cs.CV 2012
Year: 2012

We report a method for super-resolution of range images. Our approach leverages the interpretation of LR image as sparse samples on the HR grid. Based on this interpretation, we demonstrate that our recently reported approach, which reconstructs dense range images from sparse range data by exploiting a registered colour image, can be applied for the task of resolution enhancement of range images. Our method only uses a single colour image in addition to the range observation in the super-resolution process. Using the proposed approach, we demonstrate super-resolution results for large factors (e.g. 4) with good localization accuracy.
Recognizing Static Signs from the Brazilian Sign Language: Comparing Large-Margin Decision Directed Acyclic Graphs, Voting Support Vector Machines and Artificial Neural Networks
Venue: arXiv cs.CV 2012
Year: 2012

In this paper, we explore and detail our experiments in a high-dimensionality, multi-class image classification problem often found in the automatic recognition of Sign Languages. Here, our efforts are directed towards comparing the characteristics, advantages and drawbacks of creating and training Support Vector Machines disposed in a Directed Acyclic Graph and Artificial Neural Networks to classify signs from the Brazilian Sign Language (LIBRAS). We explore how the different heuristics, hyperparameters and multi-class decision schemes affect the performance, efficiency and ease of use for each classifier. We provide hyperparameter surface maps capturing accuracy and efficiency, comparisons between DDAGs and 1-vs-1 SVMs, and effects of heuristics when training ANNs with Resilient Backpropagation. We report statistically significant results using Cohen's Kappa statistic for contingency tables.
Generation of binary words avoiding alternating patterns
Venue: arXiv cs.DM 2012
Year: 2012

In this paper we propose an algorithm to generate binary words with no more 0's than 1's having a fixed number of 1's and avoiding the pattern $(10)^j1$ for any fixed $j \geq 1$. We will prove that this generation is exhaustive, that is, all such binary words are generated.
Text Classification with Compression Algorithms
Venue: arXiv cs.LG 2012
Year: 2012

This work concerns a comparison of SVM kernel methods in text categorization tasks. In particular I define a kernel function that estimates the similarity between two objects computing by their compressed lengths. In fact, compression algorithms can detect arbitrarily long dependencies within the text strings. Data text vectorization looses information in feature extractions and is highly sensitive by textual language. Furthermore, these methods are language independent and require no text preprocessing. Moreover, the accuracy computed on the datasets (Web-KB, 20ng and Reuters-21578), in some case, is greater than Gaussian, linear and polynomial kernels. The method limits are represented by computational time complexity of the Gram matrix and by very poor performance on non-textual datasets.
Refined support and entropic uncertainty inequalities
Venue: arXiv cs.IT 2012
Year: 2012

Generalized versions of the entropic (Hirschman-Beckner) and support (Elad-Bruckstein) uncertainty principle are presented for frames representations. Moreover, a sharpened version of the support inequality has been obtained by introducing a generalization of the coherence. In the finite dimensional case and under certain conditions, minimizers of this inequalities are given as constant functions on their support. In addition, $\ell^p$-norms inequalities are introduced as byproducts of the entropic inequalities.
An interactive programme for Steiner trees
Venue: arXiv cs.CG 2012
Year: 2012

We introduce a fully written programmed code with a supervised method for generating Steiner trees. Our choice of the programming language, and the use of well-known theorems from Geometry and Complex Analysis, allowed this method to be implemented with only 747 lines of effective source code. This eases the understanding and the handling of this beta version for future developments.
Architectural innovation: A game-theoretic approach
Venue: arXiv cs.NI 2012
Year: 2012

In this paper, we view the Internet under a game-theoretic lens in an effort to explain and overcome the Internet's innovation slump. Game Theory is used to model Internet environments as problems of technological competition toward the end of understanding their emergent phenomena and the evolutionary forces that shape them. However, our results extend beyond understanding the Internet architecture toward helping the Internet population achieve socially desirable outcomes.
A Synthesis Method for Quaternary Quantum Logic Circuits
Venue: arXiv cs.OH 2012
Year: 2012

Synthesis of quaternary quantum circuits involves basic quaternary gates and logic operations in the quaternary quantum domain. In this paper, we propose new projection operations and quaternary logic gates for synthesizing quaternary logic functions. We also demonstrate the realization of the proposed gates using basic quantum quaternary operations. We then employ our synthesis method to design of quaternary adder and some benchmark circuits. Our results in terms of circuit cost, are better than the existing works.
Quantitative Questions on Attack-Defense Trees
Venue: arXiv cs.CR 2012
Year: 2012

Attack-defense trees are a novel methodology for graphical security modeling and assessment. The methodology includes visual, intuitive tree models whose analysis is supported by a rigorous mathematical formalism. Both, the intuitive and the formal components of the approach can be used for quantitative analysis of attack-defense scenarios. In practice, we use intuitive questions to ask about aspects of scenarios we are interested in. Formally, a computational procedure, defined with the help of attribute domains and a bottom-up algorithm, is applied to derive the corresponding numerical values. This paper bridges the gap between the intuitive and the formal way of quantitatively assessing attack-defense scenarios. We discuss how to properly specify a question, so that it can be answered unambiguously. Given a well specified question, we then show how to derive an appropriate attribute domain which constitutes the corresponding formal model. Since any attack tree is in particular an attack-defense tree, our analysis is also an advancement of the attack tree methodology.
Eigenvalue-based Cyclostationary Spectrum Sensing Using Multiple Antennas
Venue: arXiv cs.PF 2012
Year: 2012

In this paper, we propose a signal-selective spectrum sensing method for cognitive radio networks and specifically targeted for receivers with multiple-antenna capability. This method is used for detecting the presence or absence of primary users based on the eigenvalues of the cyclic covariance matrix of received signals. In particular, the cyclic correlation significance test is used to detect a specific signal-of-interest by exploiting knowledge of its cyclic frequencies. The analytical threshold for achieving constant false alarm rate using this detection method is presented, verified through simulations, and shown to be independent of both the number of samples used and the noise variance, effectively eliminating the dependence on accurate noise estimation. The proposed method is also shown, through numerical simulations, to outperform existing multiple-antenna cyclostationary-based spectrum sensing algorithms under a quasi-static Rayleigh fading channel, in both spatially correlated and uncorrelated noise environments. The algorithm also has significantly lower computational complexity than these other approaches.
Pipelined Workflow in Hybrid MPI/Pthread runtime for External Memory Graph Construction
Venue: arXiv cs.DB 2012
Year: 2012

Graph construction from a given set of edges is a data-intensive operator that appears in social network analysis, ontology enabled databases, and, other analytics processing. The operator represents an edge list to compressed sparse row (CSR) representation (or sometimes in adjacency list, or as clustered B-Tree storage). In this work, we show how to scale CSR construction to massive scale on SSD-enabled supercomputers such as Gordon using pipelined processing. We develop several abstraction and operations for external memory and parallel edge list and integer array processing that are utilized towards building a scalable algorithm for creating CSR representation. Our experiments demonstrate that this scheme is four to six times faster than currently available implementation. Moreover, our scheme can handle up to 8 billion edges (128GB) by using external memory as compared to prior schemes where performance degrades considerably for edge list size 26 million and beyond.
Learning in the Model Space for Fault Diagnosis
Venue: arXiv cs.LG 2012
Year: 2012

The emergence of large scaled sensor networks facilitates the collection of large amounts of real-time data to monitor and control complex engineering systems. However, in many cases the collected data may be incomplete or inconsistent, while the underlying environment may be time-varying or un-formulated. In this paper, we have developed an innovative cognitive fault diagnosis framework that tackles the above challenges. This framework investigates fault diagnosis in the model space instead of in the signal space. Learning in the model space is implemented by fitting a series of models using a series of signal segments selected with a rolling window. By investigating the learning techniques in the fitted model space, faulty models can be discriminated from healthy models using one-class learning algorithm. The framework enables us to construct fault library when unknown faults occur, which can be regarded as cognitive fault isolation. This paper also theoretically investigates how to measure the pairwise distance between two models in the model space and incorporates the model distance into the learning algorithm in the model space. The results on three benchmark applications and one simulated model for the Barcelona water distribution network have confirmed the effectiveness of the proposed framework.
The logical content of triangular bases of fuzzy sets in Łukasiewicz infinite-valued logic
Venue: arXiv cs.LO 2012
Year: 2012

Continuing to pursue a research direction that we already explored in connection with Gödel-Dummett logic and Ruspini partitions, we show here that Łukasiewicz logic is able to express the notion of pseudo-triangular basis of fuzzy sets, a mild weakening of the standard notion of triangular basis. En route to our main result we obtain an elementary, logic-independent characterisation of triangular bases of fuzzy sets.
General BER Expression for One-Dimensional Constellations
Venue: arXiv cs.IT 2012
Year: 2012

A novel general ready-to-use bit-error rate (BER) expression for one-dimensional constellations is developed. The BER analysis is performed for bit patterns that form a labeling. The number of patterns for equally spaced M-PAM constellations with different BER is analyzed.
Optimal size, freshness and time-frame for voice search vocabulary
Venue: arXiv cs.CL 2012
Year: 2012

In this paper, we investigate how to optimize the vocabulary for a voice search language model. The metric we optimize over is the out-of-vocabulary (OoV) rate since it is a strong indicator of user experience. In a departure from the usual way of measuring OoV rates, web search logs allow us to compute the per-session OoV rate and thus estimate the percentage of users that experience a given OoV rate. Under very conservative text normalization, we find that a voice search vocabulary consisting of 2 to 2.5 million words extracted from 1 week of search query data will result in an aggregate OoV rate of 1%; at that size, the same OoV rate will also be experienced by 90% of users. The number of words included in the vocabulary is a stable indicator of the OoV rate. Altering the freshness of the vocabulary or the duration of the time window over which the training data is gathered does not significantly change the OoV rate. Surprisingly, a significantly larger vocabulary (approximately 10 million words) is required to guarantee OoV rates below 1% for 95% of the users.
Joining relations under discrete uncertainty
Venue: arXiv cs.DB 2012
Year: 2012

In this paper we introduce and experimentally compare alternative algorithms to join uncertain relations. Different algorithms are based on specific principles, e.g., sorting, indexing, or building intermediate relational tables to apply traditional approaches. As a consequence their performance is affected by different features of the input data, and each algorithm is shown to be more efficient than the others in specific cases. In this way statistics explicitly representing the amount and kind of uncertainty in the input uncertain relations can be used to choose the most efficient algorithm.
Approximating $k$-Median via Pseudo-Approximation
Venue: arXiv cs.DS 2012
Year: 2012

We present a novel approximation algorithm for $k$-median that achieves an approximation guarantee of $1+\sqrt{3}+ε$, improving upon the decade-old ratio of $3+ε$. Our approach is based on two components, each of which, we believe, is of independent interest. First, we show that in order to give an $α$-approximation algorithm for $k$-median, it is sufficient to give a \emph{pseudo-approximation algorithm} that finds an $α$-approximate solution by opening $k+O(1)$ facilities. This is a rather surprising result as there exist instances for which opening $k+1$ facilities may lead to a significant smaller cost than if only $k$ facilities were opened. Second, we give such a pseudo-approximation algorithm with $α= 1+\sqrt{3}+ε$. Prior to our work, it was not even known whether opening $k + o(k)$ facilities would help improve the approximation ratio.
Non-redundant random generation algorithms for weighted context-free languages
Venue: arXiv cs.FL 2012
Year: 2012

We address the non-redundant random generation of $k$ words of length $n$ in a context-free language. Additionally, we want to avoid a predefined set of words. We study a rejection-based approach, whose worst-case time complexity is shown to grow exponentially with $k$ for some specifications and in the limit case of a coupon collector. We propose two algorithms respectively based on the recursive method and on an unranking approach. We show how careful implementations of these algorithms allow for a non-redundant generation of $k$ words of length $n$ in $\mathcal{O}(k\cdot n\cdot \log{n})$ arithmetic operations, after a precomputation of $Θ(n)$ numbers. The overall complexity is therefore dominated by the generation of $k$ words, and the non-redundancy comes at a negligible cost.
Multiple Antenna Cyclostationary Spectrum Sensing Based on the Cyclic Correlation Significance Test
Venue: arXiv cs.PF 2012
Year: 2012

In this paper, we propose and analyze a spectrum sensing method based on cyclostationarity specifically targeted for receivers with multiple antennas. This detection method is used for determining the presence or absence of primary users in cognitive radio networks based on the eigenvalues of the cyclic covariance matrix of received signals. In particular, the cyclic correlation significance test is used to detect a specific signal-of-interest by exploiting knowledge of its cyclic frequencies. Analytical expressions for the probability of detection and probability of false-alarm under both spatially uncorrelated or spatially correlated noise are derived and verified by simulation. The detection performance in a Rayleigh flat-fading environment is found and verified through simulations. One of the advantages of the proposed method is that the detection threshold is shown to be independent of both the number of samples and the noise covariance, effectively eliminating the dependence on accurate noise estimation. The proposed method is also shown to provide higher detection probability and better robustness to noise uncertainty than existing multiple-antenna cyclostationary-based spectrum sensing algorithms under both AWGN as well as a quasi-static Rayleigh fading channel.
High-Order Discontinuous Galerkin Methods by GPU Metaprogramming
Venue: arXiv cs.MS 2012
Year: 2012

Discontinuous Galerkin (DG) methods for the numerical solution of partial differential equations have enjoyed considerable success because they are both flexible and robust: They allow arbitrary unstructured geometries and easy control of accuracy without compromising simulation stability. In a recent publication, we have shown that DG methods also adapt readily to execution on modern, massively parallel graphics processors (GPUs). A number of qualities of the method contribute to this suitability, reaching from locality of reference, through regularity of access patterns, to high arithmetic intensity. In this article, we illuminate a few of the more practical aspects of bringing DG onto a GPU, including the use of a Python-based metaprogramming infrastructure that was created specifically to support DG, but has found many uses across all disciplines of computational science.
Project G.N.O.S.I.S.: Geographical Network Of Synoptic Information System
Venue: arXiv cs.OH 2012
Year: 2012

Everybody knows how much synoptic maps are useful today. An excellent example above all is Google Earth: its simplicity and friendly interface allows every user to have the Earth maps ready in just one simple layout; nevertheless a crucial dimension is missing in Google Earth: the time. This doesn't mean we simply aim to add history to Google Earth (though it could be already a nice goal): the main idea behind GNOSIS project is to produce applications to "dress up" the Globe with a set of skin-maps representing the most various different kind of histories like the evolution of geology, genetics, agriculture, ethnology, linguistics, musicology, metallurgy and so forth, in time. It may be interesting in the near future to have such a possibility to watch on the map the positions and movements of the armies during the battles of Waterloo or Thermopylae, the spreading of the cultivation of corn in time, the rise and fall of Roman Empire or the diffusion of Smallpox together with the spread of a religion, a specific dialect, the early pottery techniques or the natural resources available to pre-Columbian civilizations on a Google-Earth-map-like, that is to say to have at one's hand the ultimate didactic-enciclopedic tool. To do so we foresee the use of a general-purpose intermediate/high level programming language, possibly object-oriented such C++ or Java.
Non-Malleable Condensers for Arbitrary Min-Entropy, and Almost Optimal Protocols for Privacy Amplification
Venue: arXiv cs.CR 2012
Year: 2012

Recently, the problem of privacy amplification with an active adversary has received a lot of attention. Given a shared n-bit weak random source X with min-entropy k and a security parameter s, the main goal is to construct an explicit 2-round privacy amplification protocol that achieves entropy loss O(s). Dodis and Wichs \cite{DW09} showed that optimal protocols can be achieved by constructing explicit non-malleable extractors. However, the best known explicit non-malleable extractor only achieves k=0.49n \cite{Li12b} and evidence in \cite{Li12b} suggests that constructing explicit non-malleable extractors for smaller min-entropy may be hard. In an alternative approach, Li \cite{Li12} introduced the notion of a non-malleable condenser and showed that explicit non-malleable condensers also give optimal privacy amplification protocols. In this paper, we give the first construction of non-malleable condensers for arbitrary min-entropy. Using our construction, we obtain a 2-round privacy amplification protocol with optimal entropy loss for security parameter up to s=Ω(\sqrt{k}). This is the first protocol that simultaneously achieves optimal round complexity and optimal entropy loss for arbitrary min-entropy k. We also generalize this result to obtain a protocol that runs in O(s/\sqrt{k}) rounds with optimal entropy loss, for security parameter up to s=Ω(k). This significantly improves the protocol in \cite{ckor}. Finally, we give a better non-malleable condenser for linear min-entropy, and in this case obtain a 2-round protocol with optimal entropy loss for security parameter up to s=Ω(k), which improves the entropy loss and communication complexity of the protocol in \cite{Li12b}.
Shaping Operations to Attack Robust Terror Networks
Venue: arXiv cs.SI 2012
Year: 2012

Security organizations often attempt to disrupt terror or insurgent networks by targeting "high value targets" (HVT's). However, there have been numerous examples that illustrate how such networks are able to quickly re-generate leadership after such an operation. Here, we introduce the notion of a "shaping" operation in which the terrorist network is first targeted for the purpose of reducing its leadership re-generation ability before targeting HVT's. We look to conduct shaping by maximizing the network-wide degree centrality through node removal. We formally define this problem and prove solving it is NP-Complete. We introduce a mixed integer-linear program that solves this problem exactly as well as a greedy heuristic for more practical use. We implement the greedy heuristic and found in examining five real-world terrorist networks that removing only 12% of nodes can increase the network-wide centrality between 17% and 45%. We also show our algorithm can scale to large social networks of 1,133 nodes and 5,541 edges on commodity hardware.
Faster Approximation of Max Flow for Directed Graphs
Venue: arXiv cs.DM 2012
Year: 2012

I extend the methods in "Electrical Flows, Laplacian Systems, and Faster Approximation of Maximum Flow in Undirected Graphs, with Paul Christiano, Jonathan Kelner, Daniel Spielman, and Shang-Hua Teng" to directed graphs with a variation of the framework in the paper, which lead to an algorithm that approximately solves the directed max flow problem in nearly-linear time.
Phase Retrieval: Stability and Recovery Guarantees
Venue: arXiv cs.IT 2012
Year: 2012

We consider stability and uniqueness in real phase retrieval problems over general input sets. Specifically, we assume the data consists of noisy quadratic measurements of an unknown input x in R^n that lies in a general set T and study conditions under which x can be stably recovered from the measurements. In the noise-free setting we derive a general expression on the number of measurements needed to ensure that a unique solution can be found in a stable way, that depends on the set T through a natural complexity parameter. This parameter can be computed explicitly for many sets T of interest. For example, for k-sparse inputs we show that O(k\log(n/k)) measurements are needed, and when x can be any vector in R^n, O(n) measurements suffice. In the noisy case, we show that if one can find a value for which the empirical risk is bounded by a given, computable constant (that depends on the set T), then the error with respect to the true input is bounded above by an another, closely related complexity parameter of the set. By choosing an appropriate number N of measurements, this bound can be made arbitrarily small, and it decays at a rate faster than N^{-1/2+δ} for any δ>0. In particular, for k-sparse vectors stable recovery is possible from O(k\log(n/k)\log k) noisy measurements, and when x can be any vector in R^n, O(n \log n) noisy measurements suffice. We also show that the complexity parameter for the quadratic problem is the same as the one used for analyzing stability in linear measurements under very general conditions. Thus, no substantial price has to be paid in terms of stability if there is no knowledge of the phase.