OpenRaiser/Intern-Atlas huggingface dataset:
A Dynamic Clustering and Resource Allocation Algorithm for Downlink CoMP Systems with Multiple Antenna UEs
Venue: arXiv cs.IT 2013
Year: 2013

Coordinated multi-point (CoMP) schemes have been widely studied in the recent years to tackle the inter-cell interference. In practice, latency and throughput constraints on the backhaul allow the organization of only small clusters of base stations (BSs) where joint processing (JP) can be implemented. In this work we focus on downlink CoMP-JP with multiple antenna user equipments (UEs) and propose a novel dynamic clustering algorithm. The additional degrees of freedom at the UE can be used to suppress the residual interference by using an interference rejection combiner (IRC) and allow a multistream transmission. In our proposal we first define a set of candidate clusters depending on long-term channel conditions. Then, in each time block, we develop a resource allocation scheme by jointly optimizing transmitter and receiver where: a) within each candidate cluster a weighted sum rate is estimated and then b) a set of clusters is scheduled in order to maximize the system weighted sum rate. Numerical results show that much higher rates are achieved when UEs are equipped with multiple antennas. Moreover, as this performance improvement is mainly due to the IRC, the gain achieved by the proposed approach with respect to the non-cooperative scheme decreases by increasing the number of UE antennas.
A Generalized Markov-Chain Modelling Approach to $(1,λ)$-ES Linear Optimization
Venue: arXiv cs.DM 2013
Year: 2013

The manuscript generalizes several recent results of the 2nd author concerning Markov-Chain Modelling of $(1,λ)$-ES Linear Optimization.
Distributed Connectivity Decomposition
Venue: arXiv cs.DS 2013
Year: 2013

We present time-efficient distributed algorithms for decomposing graphs with large edge or vertex connectivity into multiple spanning or dominating trees, respectively. As their primary applications, these decompositions allow us to achieve information flow with size close to the connectivity by parallelizing it along the trees. More specifically, our distributed decomposition algorithms are as follows: (I) A decomposition of each undirected graph with vertex-connectivity $k$ into (fractionally) vertex-disjoint weighted dominating trees with total weight $Ω(\frac{k}{\log n})$, in $\widetilde{O}(D+\sqrt{n})$ rounds. (II) A decomposition of each undirected graph with edge-connectivity $λ$ into (fractionally) edge-disjoint weighted spanning trees with total weight $\lceil\frac{λ-1}{2}\rceil(1-\varepsilon)$, in $\widetilde{O}(D+\sqrt{nλ})$ rounds. We also show round complexity lower bounds of $\tildeΩ(D+\sqrt{\frac{n}{k}})$ and $\tildeΩ(D+\sqrt{\frac{n}λ})$ for the above two decompositions, using techniques of [Das Sarma et al., STOC'11]. Moreover, our vertex-connectivity decomposition extends to centralized algorithms and improves the time complexity of [Censor-Hillel et al., SODA'14] from $O(n^3)$ to near-optimal $\tilde{O}(m)$. As corollaries, we also get distributed oblivious routing broadcast with $O(1)$-competitive edge-congestion and $O(\log n)$-competitive vertex-congestion. Furthermore, the vertex connectivity decomposition leads to near-time-optimal $O(\log n)$-approximation of vertex connectivity: centralized $\widetilde{O}(m)$ and distributed $\tilde{O}(D+\sqrt{n})$. The former moves toward the 1974 conjecture of Aho, Hopcroft, and Ullman postulating an $O(m)$ centralized exact algorithm while the latter is the first distributed vertex connectivity approximation.
Reducing Linear Programs into Min-max Problems
Venue: arXiv cs.CG 2013
Year: 2013

We show how to reduce a general, strictly-feasible LP problem, into a min-max problem, which can be solved by the algorithm from the third section of my thesis.
Composable Languages for Bioinformatics: The NYoSh experiment
Venue: arXiv cs.SE 2013
Year: 2013

Language workbenches are software engineering tools that help domain experts develop solutions to various classes of problems. Some of these tools focus on non-technical users and provide languages to help organize knowledge while other workbenches provide means to create new programming languages. A key advantage of language workbenches is that they support the composition of independently developed languages. This capability is useful when developing programs that can benefit from different levels of abstraction. We reasoned that language workbenches could be useful to develop bioinformatics software solutions. In order to evaluate the potential of language workbenches in bioinformatics, we tested a prominent workbench by developing an alternative to shell scripting. While shell scripts are widely used in bioinformatics to automate computational analysis, existing scripting languages do not provide many of the features present in modern programming languages. We report on our design of NYoSh (Not Your ordinary Shell). NYoSh was implemented as a collection of languages that can be composed to write programs as expressive and concise as shell scripts. NYoSh offers a concrete illustration of the advantages that language workbench technologies can bring to bioinformatics. For instance, NYoSh scripts can be edited with an environment-aware editor that provides semantic error detection and can be compiled interactively with an automatic build and deployment system. In contrast to shell scripts, NYoSh scripts can be written in a modern development environment, supporting context dependent intentions and can be extended seamlessly with new abstractions and language constructs. We demonstrate language extension and composition by presenting a tight integration of NYoSh scripts with the GobyWeb system. The NYoSh Workbench prototype is distributed at http://nyosh.campagnelab.org
Adaptive Learning of Region-based pLSA Model for Total Scene Annotation
Venue: arXiv cs.CV 2013
Year: 2013

In this paper, we present a region-based pLSA model to accomplish the task of total scene annotation. To be more specific, we not only properly generate a list of tags for each image, but also localizing each region with its corresponding tag. We integrate advantages of different existing region-based works: employ efficient and powerful JSEG algorithm for segmentation so that each region can easily express meaningful object information; the introduction of pLSA model can help better capturing semantic information behind the low-level features. Moreover, we also propose an adaptive padding mechanism to automatically choose the optimal padding strategy for each region, which directly increases the overall system performance. Finally we conduct 3 experiments to verify our ideas on Corel database and demonstrate the effectiveness and accuracy of our system.
Outage Minimization via Power Adaptation and Allocation for Truncated Hybrid ARQ
Venue: arXiv cs.IT 2013
Year: 2013

In this work, we analyze hybrid ARQ (HARQ) protocols over the independent block fading channel. We assume that the transmitter is unaware of the channel state information (CSI) but has a knowledge about the channel statistics. We consider two scenarios with respect to the feedback received by the transmitter: i) ''conventional'', one-bit feedback about the decoding success/failure (ACK/NACK), and ii) the multi-bit feedback scheme when, on top of ACK/NACK, the receiver provides additional information about the state of the decoder to the transmitter. In both cases, the feedback is used to allocate (in the case of one-bit feedback) or adapt (in the case of multi-bit feedback) the power across the HARQ transmission attempts. The objective in both cases is the minimization of the outage probability under long-term average and peak power constraints. We cast the problems into the dynamic programming (DP) framework and solve them for Nakagami-m fading channels. A simplified solution for the high signal-to-noise ratio (SNR) regime is presented using a geometric programming (GP) approach. The obtained results quantify the advantage of the multi-bit feedback over the conventional approach, and show that the power optimization can provide significant gains over conventional power-constant HARQ transmissions even in the presence of peak-power constraints.
Scalable Data Cube Analysis over Big Data
Venue: arXiv cs.DB 2013
Year: 2013

Data cubes are widely used as a powerful tool to provide multidimensional views in data warehousing and On-Line Analytical Processing (OLAP). However, with increasing data sizes, it is becoming computationally expensive to perform data cube analysis. The problem is exacerbated by the demand of supporting more complicated aggregate functions (e.g. CORRELATION, Statistical Analysis) as well as supporting frequent view updates in data cubes. This calls for new scalable and efficient data cube analysis systems. In this paper, we introduce HaCube, an extension of MapReduce, designed for efficient parallel data cube analysis on large-scale data by taking advantages from both MapReduce (in terms of scalability) and parallel DBMS (in terms of efficiency). We also provide a general data cube materialization algorithm which is able to facilitate the features in MapReduce-like systems towards an efficient data cube computation. Furthermore, we demonstrate how HaCube supports view maintenance through either incremental computation (e.g. used for SUM or COUNT) or recomputation (e.g. used for MEDIAN or CORRELATION). We implement HaCube by extending Hadoop and evaluate it based on the TPC-D benchmark over billions of tuples on a cluster with over 320 cores. The experimental results demonstrate the efficiency, scalability and practicality of HaCube for cube analysis over a large amount of data in a distributed environment.
Sensing and Recognition When Primary User Has Multiple Power Levels
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, we present a new cognitive radio (CR) scenario when the primary user (PU) operates under more than one transmit power levels. Different from the existing studies where PU is assumed to have only one constant transmit power, the new consideration well matches the practical standards, i.e., IEEE 802.11 Series, GSM, LTE, LTE-A, etc., as well as the adaptive power concept that has been studied over the past decades. The primary target in this new CR scenario is, of course, still to detect the presence of PU. However, there appears a secondary target as to identify the PU's transmit power level. Compared to the existing works where the secondary user (SU) only senses the ``on-off'' status of PU, recognizing the power level of PU achieves more ``cognition", and could be utilized to protect different powered PU with different interference levels. We derived quite many closed-form results for either the threshold expressions or the performance analysis, from which many interesting points and discussions are raised. We then further study the cooperative sensing strategy in this new cognitive scenario and show its significant difference from traditional algorithms. Numerical examples are provided to corroborate the proposed studies.
The Ergodicity of the Collatz Process in Positive Integer Field
Venue: arXiv cs.CC 2013
Year: 2013

The $3x+1$ problem, also called the Collatz conjecture, is a very interesting unsolved mathematical problem related to computer science. This paper generalized this problem by relaxing the constraints, i.e., generalizing this deterministic process to non-deterministic process, and set up three models. This paper analyzed the ergodicity of these models and proved that the ergodicity of the Collatz process in positive integer field holds, i.e., all the positive integers can be transformed to 1 by the iterations of the Collatz function.
Distributed Multiscale Computing with MUSCLE 2, the Multiscale Coupling Library and Environment
Venue: arXiv cs.DC 2013
Year: 2013

We present the Multiscale Coupling Library and Environment: MUSCLE 2. This multiscale component-based execution environment has a simple to use Java, C++, C, Python and Fortran API, compatible with MPI, OpenMP and threading codes. We demonstrate its local and distributed computing capabilities and compare its performance to MUSCLE 1, file copy, MPI, MPWide, and GridFTP. The local throughput of MPI is about two times higher, so very tightly coupled code should use MPI as a single submodel of MUSCLE 2; the distributed performance of GridFTP is lower, especially for small messages. We test the performance of a canal system model with MUSCLE 2, where it introduces an overhead as small as 5% compared to MPI.
Deciding $k$CFA is complete for EXPTIME
Venue: arXiv cs.PL 2013
Year: 2013

We give an exact characterization of the computational complexity of the $k$CFA hierarchy. For any $k > 0$, we prove that the control flow decision problem is complete for deterministic exponential time. This theorem validates empirical observations that such control flow analysis is intractable. It also provides more general insight into the complexity of abstract interpretation.
Neural Network Application on Foliage Plant Identification
Venue: arXiv cs.CV 2013
Year: 2013

Several researches in leaf identification did not include color information as features. The main reason is caused by a fact that they used green colored leaves as samples. However, for foliage plants, plants with colorful leaves, fancy patterns in their leaves, and interesting plants with unique shape, color and also texture could not be neglected. For example, Epipremnum pinnatum 'Aureum' and Epipremnum pinnatum 'Marble Queen' have similar patterns, same shape, but different colors. Combination of shape, color, texture features, and other attribute contained on the leaf is very useful in leaf identification. In this research, Polar Fourier Transform and three kinds of geometric features were used to represent shape features, color moments that consist of mean, standard deviation, skewness were used to represent color features, texture features are extracted from GLCMs, and vein features were added to improve performance of the identification system. The identification system uses Probabilistic Neural Network (PNN) as a classifier. The result shows that the system gives average accuracy of 93.0833% for 60 kinds of foliage plants.
Ways of Listening and Modes of Being: Electroacoustic Auditory Display
Venue: arXiv cs.HC 2013
Year: 2013

Auditory display is concerned with the use of non-speech sound to communicate information. If the term seems at first oxymoronic, then consider auditory display as an activity of perceptualization, that is, the process of making perceptible to humans aspects or features of a given data set or system. Most commonly this is done using visual representations (which process we call visualization) but it is not limited to the visual channel and recent years have witnessed the increased use of auditory representations in the production of tools for exploring data. By way of semiotics and an aesthetic perspective shift this article posits that auditory display may be considered a form of organized sound and explores the listening experience in this context.
Objets Sonores: Une Représentation Bio-Inspirée Hiérarchique Parcimonieuse À Très Grandes Dimensions Utilisable En Reconnaissance; Auditory Objects: Bio-Inspired Hierarchical Sparse High Dimensional Representation for Recognition
Venue: arXiv cs.SD 2013
Year: 2013

L'accent est placé dans cet article sur la structure hiérarchique, l'aspect parcimonieux de la représentation de l'information sonore, la très grande dimension des caractéristiques ainsi que sur l'indépendance des caractéristiques permettant de définir les composantes des objets sonores. Les notions d'objet sonore et de représentation neuronale sont d'abord introduites, puis illustrées avec une application en analyse de signaux sonores variés: parole, musique et environnements naturels extérieurs. Finalement, un nouveau système de reconnaissance automatique de parole est proposé. Celui-ci est comparé à un système statistique conventionnel. Il montre très clairement que l'analyse par objets sonores introduit une grande polyvalence et robustesse en reconnaissance de parole. Cette intégration des connaissances en neurosciences et traitement des signaux acoustiques ouvre de nouvelles perspectives dans le domaine de la reconnaissance de signaux acoustiques. The emphasis is put on the hierarchical structure, independence and sparseness aspects of auditory signal representations in high-dimensional spaces, so as to define the components of auditory objects. The concept of an auditory object and its neural representation is introduced. An illustrative application then follows, consisting in the analysis of various auditory signals: speech, music and natural outdoor environments. A new automatic speech recognition (ASR) system is then proposed and compared to a conventional statistical system. The proposed system clearly shows that an object-based analysis introduces a great flexibility and robustness for the task of speech recognition. The integration of knowledge from neuroscience and acoustic signal processing brings new ways of thinking to the field of classification of acoustic signals.
GoFFish: A Sub-Graph Centric Framework for Large-Scale Graph Analytics
Venue: arXiv cs.DC 2013
Year: 2013

Large scale graph processing is a major research area for Big Data exploration. Vertex centric programming models like Pregel are gaining traction due to their simple abstraction that allows for scalable execution on distributed systems naturally. However, there are limitations to this approach which cause vertex centric algorithms to under-perform due to poor compute to communication overhead ratio and slow convergence of iterative superstep. In this paper we introduce GoFFish a scalable sub-graph centric framework co-designed with a distributed persistent graph storage for large scale graph analytics on commodity clusters. We introduce a sub-graph centric programming abstraction that combines the scalability of a vertex centric approach with the flexibility of shared memory sub-graph computation. We map Connected Components, SSSP and PageRank algorithms to this model to illustrate its flexibility. Further, we empirically analyze GoFFish using several real world graphs and demonstrate its significant performance improvement, orders of magnitude in some cases, compared to Apache Giraph, the leading open source vertex centric implementation.
A brief network analysis of Artificial Intelligence publication
Venue: arXiv cs.AI 2013
Year: 2013

In this paper, we present an illustration to the history of Artificial Intelligence(AI) with a statistical analysis of publish since 1940. We collected and mined through the IEEE publish data base to analysis the geological and chronological variance of the activeness of research in AI. The connections between different institutes are showed. The result shows that the leading community of AI research are mainly in the USA, China, the Europe and Japan. The key institutes, authors and the research hotspots are revealed. It is found that the research institutes in the fields like Data Mining, Computer Vision, Pattern Recognition and some other fields of Machine Learning are quite consistent, implying a strong interaction between the community of each field. It is also showed that the research of Electronic Engineering and Industrial or Commercial applications are very active in California. Japan is also publishing a lot of papers in robotics. Due to the limitation of data source, the result might be overly influenced by the number of published articles, which is to our best improved by applying network keynode analysis on the research community instead of merely count the number of publish.
Dynamic Model of Facial Expression Recognition based on Eigen-face Approach
Venue: arXiv cs.CV 2013
Year: 2013

Emotions are best way of communicating information; and sometimes it carry more information than words. Recently, there has been a huge interest in automatic recognition of human emotion because of its wide spread application in security, surveillance, marketing, advertisement, and human-computer interaction. To communicate with a computer in a natural way, it will be desirable to use more natural modes of human communication based on voice, gestures and facial expressions. In this paper, a holistic approach for facial expression recognition is proposed which captures the variation in facial features in temporal domain and classifies the sequence of images in different emotions. The proposed method uses Haar-like features to detect face in an image. The dimensionality of the eigenspace is reduced using Principal Component Analysis (PCA). By projecting the subsequent face images into principal eigen directions, the variation pattern of the obtained weight vector is modeled to classify it into different emotions. Owing to the variations of expressions for different people and its intensity, a person specific method for emotion recognition is followed. Using the gray scale images of the frontal face, the system is able to classify four basic emotions such as happiness, sadness, surprise, and anger.
Derivative of Rotation Matrix Direct Matrix Derivation of Well Known Formula
Venue: arXiv cs.SY 2013
Year: 2013

In motion Kinematics, it is well-known that the time derivative of a 3x3rotation matrix equals a skew-symmetric matrix multiplied by the rotation matrix where the skew symmetric matrix is a linear (matrix valued) function of the angular velocity and the rotation matrix represents the rotating motion of a frame with respect to a reference frame. The equation is widely used in engineering, e.g., robotics, control, air/spacecraft modeling, etc. However, the derivations found in the literature are indirect. Motivated by the fact that the set of 3x3rotation matrices, i.e., SO(3), is a Lie group, forming a smooth (differentiable) manifold, we describe the infinitesimal increment of the rotation matrix in terms of rotation matrices and show that the above equation immediately follows.
No Free Lunch Theorem and Bayesian probability theory: two sides of the same coin. Some implications for black-box optimization and metaheuristics
Venue: arXiv cs.LG 2013
Year: 2013

Challenging optimization problems, which elude acceptable solution via conventional calculus methods, arise commonly in different areas of industrial design and practice. Hard optimization problems are those who manifest the following behavior: a) high number of independent input variables; b) very complex or irregular multi-modal fitness; c) computational expensive fitness evaluation. This paper will focus on some theoretical issues that have strong implications for practice. I will stress how an interpretation of the No Free Lunch theorem leads naturally to a general Bayesian optimization framework. The choice of a prior over the space of functions is a critical and inevitable step in every black-box optimization.
On the Design and Analysis of Multiple View Descriptors
Venue: arXiv cs.CV 2013
Year: 2013

We propose an extension of popular descriptors based on gradient orientation histograms (HOG, computed in a single image) to multiple views. It hinges on interpreting HOG as a conditional density in the space of sampled images, where the effects of nuisance factors such as viewpoint and illumination are marginalized. However, such marginalization is performed with respect to a very coarse approximation of the underlying distribution. Our extension leverages on the fact that multiple views of the same scene allow separating intrinsic from nuisance variability, and thus afford better marginalization of the latter. The result is a descriptor that has the same complexity of single-view HOG, and can be compared in the same manner, but exploits multiple views to better trade off insensitivity to nuisance variability with specificity to intrinsic variability. We also introduce a novel multi-view wide-baseline matching dataset, consisting of a mixture of real and synthetic objects with ground truthed camera motion and dense three-dimensional geometry.