OpenRaiser/Intern-Atlas huggingface dataset:
Automated PolyU Palmprint sample Registration and Coarse Classification
Venue: arXiv cs.CV 2011
Year: 2011

Biometric based authentication for secured access to resources has gained importance, due to their reliable, invariant and discriminating features. Palmprint is one such biometric entity. Prior to classification and identification registering a sample palmprint is an important activity. In this paper we propose a computationally effective method for automated registration of samples from PlolyU palmprint database. In our approach we preprocess the sample and trace the border to find the nearest point from center of sample. Angle between vector representing the nearest point and vector passing through the center is used for automated palm sample registration. The angle of inclination between start and end point of heart line and life line is used for basic classification of palmprint samples in left class and right class.
Proof nets for the Lambek-Grishin calculus
Venue: arXiv cs.CL 2011
Year: 2011

Grishin's generalization of Lambek's Syntactic Calculus combines a non-commutative multiplicative conjunction and its residuals (product, left and right division) with a dual family: multiplicative disjunction, right and left difference. Interaction between these two families takes the form of linear distributivity principles. We study proof nets for the Lambek-Grishin calculus and the correspondence between these nets and unfocused and focused versions of its sequent calculus.
High-dimensional Sparse Inverse Covariance Estimation using Greedy Methods
Venue: arXiv cs.LG 2011
Year: 2011

In this paper we consider the task of estimating the non-zero pattern of the sparse inverse covariance matrix of a zero-mean Gaussian random vector from a set of iid samples. Note that this is also equivalent to recovering the underlying graph structure of a sparse Gaussian Markov Random Field (GMRF). We present two novel greedy approaches to solving this problem. The first estimates the non-zero covariates of the overall inverse covariance matrix using a series of global forward and backward greedy steps. The second estimates the neighborhood of each node in the graph separately, again using greedy forward and backward steps, and combines the intermediate neighborhoods to form an overall estimate. The principal contribution of this paper is a rigorous analysis of the sparsistency, or consistency in recovering the sparsity pattern of the inverse covariance matrix. Surprisingly, we show that both the local and global greedy methods learn the full structure of the model with high probability given just $O(d\log(p))$ samples, which is a \emph{significant} improvement over state of the art $\ell_1$-regularized Gaussian MLE (Graphical Lasso) that requires $O(d^2\log(p))$ samples. Moreover, the restricted eigenvalue and smoothness conditions imposed by our greedy methods are much weaker than the strong irrepresentable conditions required by the $\ell_1$-regularization based methods. We corroborate our results with extensive simulations and examples, comparing our local and global greedy methods to the $\ell_1$-regularized Gaussian MLE as well as the Neighborhood Greedy method to that of nodewise $\ell_1$-regularized linear regression (Neighborhood Lasso).
Well-typed Islands Parse Faster
Venue: arXiv cs.PL 2011
Year: 2011

This paper addresses the problem of specifying and parsing the syntax of domain-specific languages (DSLs) in a modular, user-friendly way. That is, we want to enable the design of composable DSLs that combine the natural syntax of external DSLs with the easy implementation of internal DSLs. The challenge in parsing composable DSLs is that the composition of several (individually unambiguous) languages is likely to contain ambiguities. In this paper, we present the design of a system that uses a type-oriented variant of island parsing to efficiently parse the syntax of composable DSLs. In particular, we show how type-oriented island parsing is constant time with respect to the number of DSLs imported. We also show how to use our tool to implement DSLs on top of a host language such as Typed Racket.
Spam filtering by quantitative profiles
Venue: arXiv cs.IR 2011
Year: 2011

Instead of the 'bag-of-words' representation, in the quantitative profile approach to spam filtering and email categorization, an email is represented by an m-dimensional vector of numbers, with m fixed in advance. Inspired by Sroufe et al. [Sroufe, P., Phithakkitnukoon, S., Dantu, R., and Cangussu, J. (2010). Email shape analysis. In \emph{LNCS}, 5935, pp. 18-29] two instances of quantitative profiles are considered: line profile and character profile. Performance of these profiles is studied on the TREC 2007, CEAS 2008 and a private corpuses. At low computational costs, the two quantitative profiles achieve performance that is at least comparable to that of heuristic rules and naive Bayes.
Weighted-Sum-Rate-Maximizing Linear Transceiver Filters for the K-User MIMO Interference Channel
Venue: arXiv cs.IT 2011
Year: 2011

This letter is concerned with transmit and receive filter optimization for the K-user MIMO interference channel. Specifically, linear transmit and receive filter sets are designed which maximize the weighted sum rate while allowing each transmitter to utilize only the local channel state information. Our approach is based on extending the existing method of minimizing the weighted mean squared error (MSE) for the MIMO broadcast channel to the K-user interference channel at hand. For the case of the individual transmitter power constraint, however, a straightforward generalization of the existing method does not reveal a viable solution. It is in fact shown that there exists no closed-form solution for the transmit filter but simple one-dimensional parameter search yields the desired solution. Compared to the direct filter optimization using gradient-based search, our solution requires considerably less computational complexity and a smaller amount of feedback resources while achieving essentially the same level of weighted sum rate. A modified filter design is also presented which provides desired robustness in the presence of channel uncertainty
Energy Efficient Ant Colony Algorithms for Data Aggregation in Wireless Sensor Networks
Venue: arXiv cs.NI 2011
Year: 2011

In this paper, a family of ant colony algorithms called DAACA for data aggregation has been presented which contains three phases: the initialization, packet transmission and operations on pheromones. After initialization, each node estimates the remaining energy and the amount of pheromones to compute the probabilities used for dynamically selecting the next hop. After certain rounds of transmissions, the pheromones adjustment is performed periodically, which combines the advantages of both global and local pheromones adjustment for evaporating or depositing pheromones. Four different pheromones adjustment strategies are designed to achieve the global optimal network lifetime, namely Basic-DAACA, ES-DAACA, MM-DAACA and ACS-DAACA. Compared with some other data aggregation algorithms, DAACA shows higher superiority on average degree of nodes, energy efficiency, prolonging the network lifetime, computation complexity and success ratio of one hop transmission. At last we analyze the characteristic of DAACA in the aspects of robustness, fault tolerance and scalability.
An Upper Bound to the Marginal PDF of the Ordered Eigenvalues of Wishart Matrices
Venue: arXiv cs.IT 2011
Year: 2011

Diversity analysis of a number of Multiple-Input Multiple-Output (MIMO) applications requires the calculation of the expectation of a function whose variables are the ordered multiple eigenvalues of a Wishart matrix. In order to carry out this calculation, we need the marginal pdf of an arbitrary subset of the ordered eigenvalues. In this letter, we derive an upper bound to the marginal pdf of the eigenvalues. The derivation is based on the multiple integration of the well-known joint pdf, which is very complicated due to the exponential factors of the joint pdf. We suggest an alternative function that provides simpler calculation of the multiple integration. As a result, the marginal pdf is shown to be bounded by a multivariate polynomial with a given degree. After a standard bounding procedure in a Pairwise Error Probability (PEP) analysis, by applying the marginal pdf to the calculation of the expectation, the diversity order for a number of MIMO systems can be obtained in a simple manner. Simulation results that support the analysis are presented.
Mining Flipping Correlations from Large Datasets with Taxonomies
Venue: arXiv cs.DB 2011
Year: 2011

In this paper we introduce a new type of pattern -- a flipping correlation pattern. The flipping patterns are obtained from contrasting the correlations between items at different levels of abstraction. They represent surprising correlations, both positive and negative, which are specific for a given abstraction level, and which "flip" from positive to negative and vice versa when items are generalized to a higher level of abstraction. We design an efficient algorithm for finding flipping correlations, the Flipper algorithm, which outperforms naive pattern mining methods by several orders of magnitude. We apply Flipper to real-life datasets and show that the discovered patterns are non-redundant, surprising and actionable. Flipper finds strong contrasting correlations in itemsets with low-to-medium support, while existing techniques cannot handle the pattern discovery in this frequency range.
Overview of EIREX 2010: Computing
Venue: arXiv cs.IR 2011
Year: 2011

The first Information Retrieval Education through Experimentation track (EIREX 2010) was run at the University Carlos III of Madrid, during the 2010 spring semester. EIREX 2010 is the first in a series of experiments designed to foster new Information Retrieval (IR) education methodologies and resources, with the specific goal of teaching undergraduate IR courses from an experimental perspective. For an introduction to the motivation behind the EIREX experiments, see the first sections of [Urbano et al., 2011]. For information on other editions of EIREX and related data, see the website at http://ir.kr.inf.uc3m.es/eirex/. The EIREX series have the following goals: a) to help students get a view of the Information Retrieval process as they would find it in a real-world scenario, either industrial or academic; b) to make students realize the importance of laboratory experiments in Computer Science and have them initiated in their execution and analysis; c) to create a public repository of resources to teach Information Retrieval courses; d) to seek the collaboration and active participation of other Universities in this endeavor. This overview paper summarizes the results of the EIREX 2010 track, focusing on the creation of the test collection and the analysis to assess its reliability.
Compressed Beamforming Applied to B-Mode Ultrasound Imaging
Venue: arXiv cs.OH 2011
Year: 2011

Emerging sonography techniques often imply increasing in the number of transducer elements involved in the imaging process. Consequently, larger amounts of data must be acquired and processed by the beamformer. The significant growth in the amounts of data effects both machinery size and power consumption. Within the classical sampling framework, state of the art systems reduce processing rates by exploiting the bandpass bandwidth of the detected signals. It has been recently shown, that a much more significant sample-rate reduction may be obtained, by treating ultrasound signals within the Finite Rate of Innovation framework. These ideas follow the spirit of Xampling, which combines classic methods from sampling theory with recent developments in Compressed Sensing. Applying such low-rate sampling schemes to individual transducer elements, which detect energy reflected from biological tissues, is limited by the noisy nature of the signals. This often results in erroneous parameter extraction, bringing forward the need to enhance the SNR of the low-rate samples. In our work, we manage to achieve such SNR enhancement, by beamforming the sub-Nyquist samples obtained from multiple elements. We refer to this process as "compressed beamforming". Applying it to cardiac ultrasound data, we successfully image macroscopic perturbations, while achieving a nearly eight-fold reduction in sample-rate, compared to standard techniques.
Network Analysis of the French Environmental Code
Venue: arXiv cs.SI 2011
Year: 2011

We perform a detailed analysis of the network constituted by the citations in a legal code, we search for hidden structures and properties. The graph associated to the Environmental code has a small-world structure and it is partitioned in several hidden communities of articles that only partially coincide with the organization of the code as given by its table of content. Several articles are also connected with a low number of articles but are intermediate between large communities. The structure of the Environmental Code is contrasting with the reference network of all the French Legal Codes that presents a rich-club of ten codes very central to the whole French legal system, but no small-world property. This comparison shows that the structural properties of the reference network associated to a legal system strongly depends on the scale and granularity of the analysis, as is the case for many complex systems
Picture Collage with Genetic Algorithm and Stereo vision
Venue: arXiv cs.CV 2011
Year: 2011

In this paper, a salient region extraction method for creating picture collage based on stereo vision is proposed. Picture collage is a kind of visual image summary to arrange all input images on a given canvas, allowing overlay, to maximize visible visual information. The salient regions of each image are firstly extracted and represented as a depth map. The output picture collage shows as many visible salient regions (without being overlaid by others) from all images as possible. A very efficient Genetic algorithm is used here for the optimization. The experimental results showed the superior performance of the proposed method.
Using Data Warehouse to Support Building Strategy or Forecast Business Tend
Venue: arXiv cs.DB 2011
Year: 2011

The data warehousing is becoming increasingly important in terms of strategic decision making through their capacity to integrate heterogeneous data from multiple information sources in a common storage space, for querying and analysis. So it can evolve into a multi-tier structure where parts of the organization take information from the main data warehouse into their own systems. These may include analysis databases or dependent data marts. As the data warehouse evolves and the organization gets better at capturing information on all interactions with the customer. Data warehouse can track customer interactions over the whole of the customer's lifetime.
Uncovering Plagiarism Networks
Venue: arXiv cs.IT 2011
Year: 2011

Plagiarism detection in educational programming assignments is still a problematic issue in terms of resource waste, ethical controversy, legal risks, and technical complexity. This paper presents AC, a modular plagiarism detection system. The design is portable across platforms and assignment formats and provides easy extraction into the internal assignment representation. Multiple similarity measures have been incorporated, both existing and newly-developed. Statistical analysis and several graphical visualizations aid in the interpretation of analysis results. The system has been evaluated with a survey that encompasses several academic semesters of use at the authors' institution.
Optimal Scheduling of File Transfers with Divisible Sizes on Multiple Disjoint Paths
Venue: arXiv cs.DS 2012
Year: 2012

In this paper I investigate several offline and online data transfer scheduling problems and propose efficient algorithms and techniques for addressing them. In the offline case, I present a novel, heuristic, algorithm for scheduling files with divisible sizes on multiple disjoint paths, in order to maximize the total profit (the problem is equivalent to the multiple knapsack problem with divisible item sizes). I then consider a cost optimization problem for transferring a sequence of identical files, subject to time constraints imposed by the data transfer providers. For the online case I propose an algorithmic framework based on the block partitioning method, which can speed up the process of resource allocation and reservation.
On the decidability of semigroup freeness
Venue: arXiv cs.DM 2012
Year: 2012

This paper deals with the decidability of semigroup freeness. More precisely, the freeness problem over a semigroup S is defined as: given a finite subset X of S, decide whether each element of S has at most one factorization over X. To date, the decidabilities of two freeness problems have been closely examined. In 1953, Sardinas and Patterson proposed a now famous algorithm for the freeness problem over the free monoid. In 1991, Klarner, Birget and Satterfield proved the undecidability of the freeness problem over three-by-three integer matrices. Both results led to the publication of many subsequent papers. The aim of the present paper is three-fold: (i) to present general results concerning freeness problems, (ii) to study the decidability of freeness problems over various particular semigroups (special attention is devoted to multiplicative matrix semigroups), and (iii) to propose precise, challenging open questions in order to promote the study of the topic.
A bound on the size of linear codes
Venue: arXiv cs.IT 2012
Year: 2012

We present a bound on the size of linear codes. This bound is independent of other known bounds, e.g. the Griesmer bound.
Upper Bounds on the Capacities of Noncontrollable Finite-State Channels with/without Feedback
Venue: arXiv cs.IT 2012
Year: 2012

Noncontrollable finite-state channels (FSCs) are FSCs in which the channel inputs have no influence on the channel states, i.e., the channel states evolve freely. Since single-letter formulae for the channel capacities are rarely available for general noncontrollable FSCs, computable bounds are usually utilized to numerically bound the capacities. In this paper, we take the delayed channel state as part of the channel input and then define the {\em directed information rate} from the new channel input (including the source and the delayed channel state) sequence to the channel output sequence. With this technique, we derive a series of upper bounds on the capacities of noncontrollable FSCs with/without feedback. These upper bounds can be achieved by conditional Markov sources and computed by solving an average reward per stage stochastic control problem (ARSCP) with a compact state space and a compact action space. By showing that the ARSCP has a uniformly continuous reward function, we transform the original ARSCP into a finite-state and finite-action ARSCP that can be solved by a value iteration method. Under a mild assumption, the value iteration algorithm is convergent and delivers a near-optimal stationary policy and a numerical upper bound.
SuperNOVA: a novel algorithm for graph automorphism calculations
Venue: arXiv cs.DS 2012
Year: 2012

The graph isomorphism problem is of practical importance, as well as being a theoretical curiosity in computational complexity theory in that it is not known whether it is $NP$-complete or $P$. However, for many graphs, the problem is tractable, and related to the problem of finding the automorphism group of the graph. Perhaps the most well known state-of-the art implementation for finding the automorphism group is Nauty. However, Nauty is particularly susceptible to poor performance on star configurations, where the spokes of the star are isomorphic with each other. In this work, I present an algorithm that explodes these star configurations, reducing the problem to a sequence of simpler automorphism group calculations.
Matrix Completion from Noisy Entries
Venue: arXiv cs.LG 2012
Year: 2012

Given a matrix M of low-rank, we consider the problem of reconstructing it from noisy observations of a small, random subset of its entries. The problem arises in a variety of applications, from collaborative filtering (the `Netflix problem') to structure-from-motion and positioning. We study a low complexity algorithm introduced by Keshavan et al.(2009), based on a combination of spectral techniques and manifold optimization, that we call here OptSpace. We prove performance guarantees that are order-optimal in a number of circumstances.
Complexity-Efficient Enumeration Techniques for Soft-Input, Soft-Output Sphere Decoding
Venue: arXiv cs.NI 2012
Year: 2012

In this paper two complexity efficient soft sphere-decoder modifications are proposed for computing the max-log LLR values in iterative MIMO systems, which avoid the costly, typically needed, full enumeration and sorting (FES) procedure during the tree traversal without compromising the max-log performance. It is shown that despite the resulting increase in the number of expanded nodes, they can be more computationally efficient than the typical soft sphere decoders by avoiding the unnecessary complexity of FES.
On Classification from Outlier View
Venue: arXiv cs.AI 2012
Year: 2012

Classification is the basis of cognition. Unlike other solutions, this study approaches it from the view of outliers. We present an expanding algorithm to detect outliers in univariate datasets, together with the underlying foundation. The expanding algorithm runs in a holistic way, making it a rather robust solution. Synthetic and real data experiments show its power. Furthermore, an application for multi-class problems leads to the introduction of the oscillator algorithm. The corresponding result implies the potential wide use of the expanding algorithm.
L^p boundedness of the Hilbert transform
Venue: arXiv cs.IT 2012
Year: 2012

The Hilbert transform is essentially the \textit{only} singular operator in one dimension. This undoubtedly makes it one of the the most important linear operators in harmonic analysis. The Hilbert transform has had a profound bearing on several theoretical and physical problems across a wide range of disciplines; this includes problems in Fourier convergence, complex analysis, potential theory, modulation theory, wavelet theory, aerofoil design, dispersion relations and high-energy physics, to name a few. In this monograph, we revisit some of the established results concerning the global behavior of the Hilbert transform, namely that it is is weakly bounded on $\eL^1(\R)$, and strongly bounded on $\eL^p(\R)$ for $1 < p <\infty$, and provide a self-contained derivation of the same using real-variable techniques.