OpenRaiser/Intern-Atlas huggingface dataset:
Sparsity Lower Bounds for Dimensionality Reducing Maps
Venue: arXiv cs.DS 2012
Year: 2012

We give near-tight lower bounds for the sparsity required in several dimensionality reducing linear maps. First, consider the JL lemma which states that for any set of n vectors in R there is a matrix A in R^{m x d} with m = O(eps^{-2}log n) such that mapping by A preserves pairwise Euclidean distances of these n vectors up to a 1 +/- eps factor. We show that there exists a set of n vectors such that any such matrix A with at most s non-zero entries per column must have s = Omega(eps^{-1}log n/log(1/eps)) as long as m < O(n/log(1/eps)). This bound improves the lower bound of Omega(min{eps^{-2}, eps^{-1}sqrt{log_m d}}) by [Dasgupta-Kumar-Sarlos, STOC 2010], which only held against the stronger property of distributional JL, and only against a certain restricted class of distributions. Meanwhile our lower bound is against the JL lemma itself, with no restrictions. Our lower bound matches the sparse Johnson-Lindenstrauss upper bound of [Kane-Nelson, SODA 2012] up to an O(log(1/eps)) factor. Next, we show that any m x n matrix with the k-restricted isometry property (RIP) with constant distortion must have at least Omega(klog(n/k)) non-zeroes per column if the number of the rows is the optimal value m = O(klog (n/k)), and if k < n/polylog n. This improves the previous lower bound of Omega(min{k, n/m}) by [Chandar, 2010] and shows that for virtually all k it is impossible to have a sparse RIP matrix with an optimal number of rows. Lastly, we show that any oblivious distribution over subspace embedding matrices with 1 non-zero per column and preserving all distances in a d dimensional-subspace up to a constant factor with constant probability must have at least Omega(d^2) rows. This matches one of the upper bounds in [Nelson-Nguyen, 2012] and shows the impossibility of obtaining the best of both of constructions in that work, namely 1 non-zero per column and Õ(d) rows.
Soft (Gaussian CDE) regression models and loss functions
Venue: arXiv cs.LG 2012
Year: 2012

Regression, unlike classification, has lacked a comprehensive and effective approach to deal with cost-sensitive problems by the reuse (and not a re-training) of general regression models. In this paper, a wide variety of cost-sensitive problems in regression (such as bids, asymmetric losses and rejection rules) can be solved effectively by a lightweight but powerful approach, consisting of: (1) the conversion of any traditional one-parameter crisp regression model into a two-parameter soft regression model, seen as a normal conditional density estimator, by the use of newly-introduced enrichment methods; and (2) the reframing of an enriched soft regression model to new contexts by an instance-dependent optimisation of the expected loss derived from the conditional normal distribution.
How Robust are Linear Sketches to Adaptive Inputs?
Venue: arXiv cs.DS 2012
Year: 2012

Linear sketches are powerful algorithmic tools that turn an n-dimensional input into a concise lower-dimensional representation via a linear transformation. Such sketches have seen a wide range of applications including norm estimation over data streams, compressed sensing, and distributed computing. In almost any realistic setting, however, a linear sketch faces the possibility that its inputs are correlated with previous evaluations of the sketch. Known techniques no longer guarantee the correctness of the output in the presence of such correlations. We therefore ask: Are linear sketches inherently non-robust to adaptively chosen inputs? We give a strong affirmative answer to this question. Specifically, we show that no linear sketch approximates the Euclidean norm of its input to within an arbitrary multiplicative approximation factor on a polynomial number of adaptively chosen inputs. The result remains true even if the dimension of the sketch is d = n - o(n) and the sketch is given unbounded computation time. Our result is based on an algorithm with running time polynomial in d that adaptively finds a distribution over inputs on which the sketch is incorrect with constant probability. Our result implies several corollaries for related problems including lp-norm estimation and compressed sensing. Notably, we resolve an open problem in compressed sensing regarding the feasibility of l2/l2-recovery guarantees in the presence of computationally bounded adversaries.
An effective web document clustering for information retrieval
Venue: arXiv cs.IR 2012
Year: 2012

The size of web has increased exponentially over the past few years with thousands of documents related to a subject available to the user. With this much amount of information available, it is not possible to take the full advantage of the World Wide Web without having a proper framework to search through the available data. This requisite organization can be done in many ways. In this paper we introduce a combine approach to cluster the web pages which first finds the frequent sets and then clusters the documents. These frequent sets are generated by using Frequent Pattern growth technique. Then by applying Fuzzy C- Means algorithm on it, we found clusters having documents which are highly related and have similar features. We used Gensim package to implement our approach because of its simplicity and robust nature. We have compared our results with the combine approach of (Frequent Pattern growth, K-means) and (Frequent Pattern growth, Cosine_Similarity). Experimental results show that our approach is more efficient then the above two combine approach and can handles more efficiently the serious limitation of traditional Fuzzy C-Means algorithm, which is sensitiveto initial centroid and the number of clusters to be formed.
Detection-Directed Sparse Estimation using Bayesian Hypothesis Test and Belief Propagation
Venue: arXiv cs.IT 2012
Year: 2012

In this paper, we propose a sparse recovery algorithm called detection-directed (DD) sparse estimation using Bayesian hypothesis test (BHT) and belief propagation (BP). In this framework, we consider the use of sparse-binary sensing matrices which has the tree-like property and the sampled-message approach for the implementation of BP. The key idea behind the proposed algorithm is that the recovery takes DD-estimation structure consisting of two parts: support detection and signal value estimation. BP and BHT perform the support detection, and an MMSE estimator finds the signal values using the detected support set. The proposed algorithm provides noise-robustness against measurement noise beyond the conventional MAP approach, as well as a solution to remove quantization effect by the sampled-message based BP independently of memory size for the message sampling. We explain how the proposed algorithm can have the aforementioned characteristics via exemplary discussion. In addition, our experiments validate such superiority of the proposed algorithm, compared to recent algorithms under noisy setup. Interestingly the experimental results show that performance of the proposed algorithm approaches that of the oracle estimator as SNR becomes higher.
Time-bounded Reachability for Hybrid Automata: Complexity and Fixpoints
Venue: arXiv cs.LO 2012
Year: 2012

In this paper, we study thetime-bounded reachability problem for rectangular hybrid automata with non-negative rates (RHA+). This problem was recently shown to be decidable [Brihaye et al, ICALP11] (even though the unbounded reachability problem for even very simple classes of hybrid automata is well-known to be undecidable). However, [Brihaye et al, ICALP11] does not provide a precise characterisation of the complexity of the time-bounded reachability problem. The contribution of the present paper is threefold. First, we provide a new NExpTime algorithm to solve the timed-bounded reachability problem on RHA+. This algorithm improves on the one of [Brihaye et al, ICALP11] by at least one exponential. Second, we show that this new algorithm is optimal, by establishing a matching lower bound: time-bounded reachability for RHA+ is therefore NExpTime-complete. Third, we extend these results in a practical direction, by showing that we can effectively compute fixpoints that characterise the sets of states that are reachable (resp. co-reachable) within T time units from a given starting state.
Shattering, Graph Orientations, and Connectivity
Venue: arXiv cs.DS 2012
Year: 2012

We present a connection between two seemingly disparate fields: VC-theory and graph theory. This connection yields natural correspondences between fundamental concepts in VC-theory, such as shattering and VC-dimension, and well-studied concepts of graph theory related to connectivity, combinatorial optimization, forbidden subgraphs, and others. In one direction, we use this connection to derive results in graph theory. Our main tool is a generalization of the Sauer-Shelah Lemma. Using this tool we obtain a series of inequalities and equalities related to properties of orientations of a graph. Some of these results appear to be new, for others we give new and simple proofs. In the other direction, we present new illustrative examples of shattering-extremal systems - a class of set-systems in VC-theory whose understanding is considered by some authors to be incomplete. These examples are derived from properties of orientations related to distances and flows in networks.
Composable and Efficient Mechanisms
Venue: arXiv cs.GT 2012
Year: 2012

We initiate the study of efficient mechanism design with guaranteed good properties even when players participate in multiple different mechanisms simultaneously or sequentially. We define the class of smooth mechanisms, related to smooth games defined by Roughgarden, that can be thought of as mechanisms that generate approximately market clearing prices. We show that smooth mechanisms result in high quality outcome in equilibrium both in the full information setting and in the Bayesian setting with uncertainty about participants, as well as in learning outcomes. Our main result is to show that such mechanisms compose well: smoothness locally at each mechanism implies efficiency globally. For mechanisms where good performance requires that bidders do not bid above their value, we identify the notion of a weakly smooth mechanism. Weakly smooth mechanisms, such as the Vickrey auction, are approximately efficient under the no-overbidding assumption. Similar to smooth mechanisms, weakly smooth mechanisms behave well in composition, and have high quality outcome in equilibrium (assuming no overbidding) both in the full information setting and in the Bayesian setting, as well as in learning outcomes. In most of the paper we assume participants have quasi-linear valuations. We also extend some of our results to settings where participants have budget constraints.
Use of PSO in Parameter Estimation of Robot Dynamics; Part One: No Need for Parameterization
Venue: arXiv cs.RO 2012
Year: 2012

Offline procedures for estimating parameters of robot dynamics are practically based on the parameterized inverse dynamic model. In this paper, we present a novel approach to parameter estimation of robot dynamics which removes the necessity of parameterization (i.e. finding the minimum number of parameters from which the dynamics can be calculated through a linear model with respect to these parameters). This offline approach is based on a simple and powerful swarm intelligence tool: the particle swarm optimization (PSO). In this paper, we discuss and validate the method through simulated experiments. In Part Two we analyze our method in terms of robustness and compare it to robust analytical methods of estimation.
Derivation of fast DCT algorithms using algebraic technique based on Galois theory
Venue: arXiv cs.DS 2012
Year: 2012

The paper presents an algebraic technique for derivation of fast discrete cosine transform (DCT) algorithms. The technique is based on the algebraic signal processing theory (ASP). In ASP a DCT associates with a polynomial algebra C[x]/p(x). A fast algorithm is obtained as a stepwise decomposition of C[x]/p(x). In order to reveal the connection between derivation of fast DCT algorithms and Galois theory we define polynomial algebra over the field of rational numbers Q instead of complex C. The decomposition of Q[x]/p(x) requires the extension of the base field Q to splitting field E of polynomial p(x). Galois theory is used to find intermediate subfields L_i in which polynomial p(x) is factored. Based on this factorization fast DCT algorithm is derived.
Solving weighted and counting variants of connectivity problems parameterized by treewidth deterministically in single exponential time
Venue: arXiv cs.DS 2012
Year: 2012

It is well known that many local graph problems, like Vertex Cover and Dominating Set, can be solved in 2^{O(tw)}|V|^{O(1)} time for graphs G=(V,E) with a given tree decomposition of width tw. However, for nonlocal problems, like the fundamental class of connectivity problems, for a long time we did not know how to do this faster than tw^{O(tw)}|V|^{O(1)}. Recently, Cygan et al. (FOCS 2011) presented Monte Carlo algorithms for a wide range of connectivity problems running in time $c^{tw}|V|^{O(1)} for a small constant c, e.g., for Hamiltonian Cycle and Steiner tree. Naturally, this raises the question whether randomization is necessary to achieve this runtime; furthermore, it is desirable to also solve counting and weighted versions (the latter without incurring a pseudo-polynomial cost in terms of the weights). We present two new approaches rooted in linear algebra, based on matrix rank and determinants, which provide deterministic c^{tw}|V|^{O(1)} time algorithms, also for weighted and counting versions. For example, in this time we can solve the traveling salesman problem or count the number of Hamiltonian cycles. The rank-based ideas provide a rather general approach for speeding up even straightforward dynamic programming formulations by identifying "small" sets of representative partial solutions; we focus on the case of expressing connectivity via sets of partitions, but the essential ideas should have further applications. The determinant-based approach uses the matrix tree theorem for deriving closed formulas for counting versions of connectivity problems; we show how to evaluate those formulas via dynamic programming.
Image denoising with multi-layer perceptrons, part 2: training trade-offs and analysis of their mechanisms
Venue: arXiv cs.CV 2012
Year: 2012

Image denoising can be described as the problem of mapping from a noisy image to a noise-free image. In another paper, we show that multi-layer perceptrons can achieve outstanding image denoising performance for various types of noise (additive white Gaussian noise, mixed Poisson-Gaussian noise, JPEG artifacts, salt-and-pepper noise and noise resembling stripes). In this work we discuss in detail which trade-offs have to be considered during the training procedure. We will show how to achieve good results and which pitfalls to avoid. By analysing the activation patterns of the hidden units we are able to make observations regarding the functioning principle of multi-layer perceptrons trained for image denoising.
On the Parameterized and Approximation Hardness of Metric Dimension
Venue: arXiv cs.CC 2012
Year: 2012

The NP-hard Metric Dimension problem is to decide for a given graph G and a positive integer k whether there is a vertex subset of size at most k that separates all vertex pairs in G. Herein, a vertex v separates a pair {u,w} if the distance (length of a shortest path) between v and u is different from the distance of v and w. We give a polynomial-time computable reduction from the Bipartite Dominating Set problem to Metric Dimension on maximum degree three graphs such that there is a one-to-one correspondence between the solution sets of both problems. There are two main consequences of this: First, it proves that Metric Dimension on maximum degree three graphs is W[2]-complete with respect to the parameter k. This answers an open question concerning the parameterized complexity of Metric Dimension posed by Díaz et al. [ESA'12] and already mentioned by Lokshtanov [Dagstuhl seminar, 2009]. Additionally, it implies that Metric Dimension cannot be solved in n^{o(k)} time, unless the assumption FPT \neq W[1] fails. This proves that a trivial n^{O(k)} algorithm is probably asymptotically optimal. Second, as Bipartite Dominating Set is inapproximable within o(log n), it follows that Metric Dimension on maximum degree three graphs is also inapproximable by a factor of o(log n), unless NP=P. This strengthens the result of Hauptmann et al. [JDA 2012] who proved APX-hardness on bounded-degree graphs.
An Adaptive parameter free data mining approach for healthcare application
Venue: arXiv cs.DB 2012
Year: 2012

In today's world, healthcare is the most important factor affecting human life. Due to heavy work load it is not possible for personal healthcare. The proposed system acts as a preventive measure for determining whether a person is fit or unfit based on person's historical and real time data by applying clustering algorithms like K-means and D-stream. The Density-based clustering algorithm i.e. the D-stream algorithm overcomes drawbacks of K-Means algorithm. By calculating their performance measures we finally find out effectiveness and efficiency of both the algorithms. Both clustering algorithms are applied on patient's bio-medical historical database. To check the correctness of both the algorithms, we apply them on patient's current bio-medical data.
Multicasting over Overlay Networks A Critical Review
Venue: arXiv cs.NI 2012
Year: 2012

Multicasting technology uses the minimum network resources to serve multiple clients by duplicating the data packets at the closest possible point to the clients. This way at most only one data packets travels down a network link at any one time irrespective of how many clients receive this packet. Traditionally multicasting has been implemented over a specialized network built using multicast routers. This kind of network has the drawback of requiring the deployment of special routers that are more expensive than ordinary routers. Recently there is new interest in delivering multicast traffic over application layer overlay networks. Application layer overlay networks though built on top of the physical network, behave like an independent virtual network made up of only logical links between the nodes. Several authors have proposed systems, mechanisms and protocols for the implementation of multicast media streaming over overlay networks. In this paper, the author takes a critical look at these systems and mechanism with special reference to their strengths and weaknesses.
Implementation of Security in Distributed Systems - A Comparative Study
Venue: arXiv cs.DC 2012
Year: 2012

This paper presents a comparative study of distributed systems and the security issues associated with those systems. Four commonly used distributed systems were considered for detailed analysis in terms of technologies involved, security issues faced by them and solution proposed to circumvent those issues. Finally the security issues and the solutions were summarized and compared with each other.
Time Complexity Analysis of Binary Space Partitioning Scheme for Image Compression
Venue: arXiv cs.CV 2012
Year: 2012

Segmentation-based image coding methods provide high compression ratios when compared with traditional image coding approaches like the transform and sub band coding for low bit-rate compression applications. In this paper, a segmentation-based image coding method, namely the Binary Space Partition scheme, that divides the desired image using a recursive procedure for coding is presented. The BSP approach partitions the desired image recursively by using bisecting lines, selected from a collection of discrete optional lines, in a hierarchical manner. This partitioning procedure generates a binary tree, which is referred to as the BSP-tree representation of the desired image. The algorithm is extremely complex in computation and has high execution time. The time complexity of the BSP scheme is explored in this work.
MaTrust: An Effective Multi-Aspect Trust Inference Model
Venue: arXiv cs.DB 2012
Year: 2012

Trust is a fundamental concept in many real-world applications such as e-commerce and peer-to-peer networks. In these applications, users can generate local opinions about the counterparts based on direct experiences, and these opinions can then be aggregated to build trust among unknown users. The mechanism to build new trust relationships based on existing ones is referred to as trust inference. State-of-the-art trust inference approaches employ the transitivity property of trust by propagating trust along connected users. In this paper, we propose a novel trust inference model (MaTrust) by exploring an equally important property of trust, i.e., the multi-aspect property. MaTrust directly characterizes multiple latent factors for each trustor and trustee from the locally-generated trust relationships. Furthermore, it can naturally incorporate prior knowledge as specified factors. These factors in turn serve as the basis to infer the unseen trustworthiness scores. Experimental evaluations on real data sets show that the proposed MaTrust significantly outperforms several benchmark trust inference models in both effectiveness and efficiency.
Localisation of Numerical Date Field in an Indian Handwritten Document
Venue: arXiv cs.CV 2012
Year: 2012

This paper describes a method to localise all those areas which may constitute the date field in an Indian handwritten document. Spatial patterns of the date field are studied from various handwritten documents and an algorithm is developed through statistical analysis to identify those sets of connected components which may constitute the date. Common date patterns followed in India are considered to classify the date formats in different classes. Reported results demonstrate promising performance of the proposed approach
Lattices and maximum flow algorithms in planar graphs
Venue: arXiv cs.DM 2012
Year: 2012

We show that the left/right relation on the set of s-t-paths of a plane graph induces a so-called submodular lattice. If the embedding of the graph is s-t-planar, this lattice is even consecutive. This implies that Ford and Fulkerson's uppermost path algorithm for maximum flow in such graphs is indeed a special case of a two-phase greedy algorithm on lattice polyhedra. We also show that the properties submodularity and consecutivity cannot be achieved simultaneously by any partial order on the paths if the graph is planar but not s-t-planar, thus providing a characterization of this class of graphs.
Designing Rating Systems to Promote Mutual Security for Interconnected Networks
Venue: arXiv cs.GT 2012
Year: 2012

Interconnected autonomous systems often share security risks. However, an autonomous system lacks the incentive to make (sufficient) security investments if the cost exceeds its own benefit even though doing that would be socially beneficial. In this paper, we develop a systematic and rigorous framework for analyzing and significantly improving the mutual security of a collection of ASs that interact frequently over a long period of time. Using this framework, we show that simple incentive schemes based on rating systems can be designed to encourage the autonomous systems' security investments, thereby significantly improving their mutual security.