OpenRaiser/Intern-Atlas huggingface dataset:
On the Performance Limits of Scalar Coding Over MISO Channels
Venue: arXiv cs.IT 2013
Year: 2013

The performance limits of scalar coding for multiple-input single-output channels are revisited in this work. By employing randomized beamforming, Narula et al. demonstrated that the loss of scalar coding is universally bounded by ~ 2.51 dB (or 0.833 bits/symbol) for any number of antennas and channel gains. In this work, by using randomized beamforming in conjunction with space-time codes, it is shown that the bound can be tightened to ~ 1.1 dB (or 0.39 bits/symbol).
Sharp MSE Bounds for Proximal Denoising
Venue: arXiv cs.IT 2013
Year: 2013

Denoising has to do with estimating a signal $x_0$ from its noisy observations $y=x_0+z$. In this paper, we focus on the "structured denoising problem", where the signal $x_0$ possesses a certain structure and $z$ has independent normally distributed entries with mean zero and variance $σ^2$. We employ a structure-inducing convex function $f(\cdot)$ and solve $\min_x\{\frac{1}{2}\|y-x\|_2^2+σλf(x)\}$ to estimate $x_0$, for some $λ>0$. Common choices for $f(\cdot)$ include the $\ell_1$ norm for sparse vectors, the $\ell_1-\ell_2$ norm for block-sparse signals and the nuclear norm for low-rank matrices. The metric we use to evaluate the performance of an estimate $x^*$ is the normalized mean-squared-error $\text{NMSE}(σ)=\frac{\mathbb{E}\|x^*-x_0\|_2^2}{σ^2}$. We show that NMSE is maximized as $σ\rightarrow 0$ and we find the \emph{exact} worst case NMSE, which has a simple geometric interpretation: the mean-squared-distance of a standard normal vector to the $λ$-scaled subdifferential $λ\partial f(x_0)$. When $λ$ is optimally tuned to minimize the worst-case NMSE, our results can be related to the constrained denoising problem $\min_{f(x)\leq f(x_0)}\{\|y-x\|_2\}$. The paper also connects these results to the generalized LASSO problem, in which, one solves $\min_{f(x)\leq f(x_0)}\{\|y-Ax\|_2\}$ to estimate $x_0$ from noisy linear observations $y=Ax_0+z$. We show that certain properties of the LASSO problem are closely related to the denoising problem. In particular, we characterize the normalized LASSO cost and show that it exhibits a "phase transition" as a function of number of observations. Our results are significant in two ways. First, we find a simple formula for the performance of a general convex estimator. Secondly, we establish a connection between the denoising and linear inverse problems.
A faster FPT algorithm for Bipartite Contraction
Venue: arXiv cs.DS 2013
Year: 2013

The \textsc{Bipartite Contraction} problem is to decide, given a graph $G$ and a parameter $k$, whether we can can obtain a bipartite graph from $G$ by at most $k$ edge contractions. The fixed-parameter tractability of the problem was shown by [Heggernes et al. 2011], with an algorithm whose running time has double-exponential dependence on $k$. We present a new randomized FPT algorithm for the problem, which is both conceptually simpler and achieves an improved $2^{O(k^2)} n m$ running time, i.e., avoiding the double-exponential dependence on $k$. The algorithm can be derandomized using standard techniques.
Clustering Web Search Results For Effective Arabic Language Browsing
Venue: arXiv cs.IR 2013
Year: 2013

The process of browsing Search Results is one of the major problems with traditional Web search engines for English, European, and any other languages generally, and for Arabic Language particularly. This process is absolutely time consuming and the browsing style seems to be unattractive. Organizing Web search results into clusters facilitates users quick browsing through search results. Traditional clustering techniques (data-centric clustering algorithms) are inadequate since they don't generate clusters with highly readable names or cluster labels. To solve this problem, Description-centric algorithms such as Suffix Tree Clustering (STC) algorithm have been introduced and used successfully and extensively with different adapted versions for English, European, and Chinese Languages. However, till the day of writing this paper, in our knowledge, STC algorithm has been never applied for Arabic Web Snippets Search Results Clustering.In this paper, we propose first, to study how STC can be applied for Arabic Language? We then illustrate by example that is impossible to apply STC after Arabic Snippets pre-processing (stem or root extraction) because the Merging process yields many redundant clusters. Secondly, to overcome this problem, we propose to integrate STC in a new scheme taking into a count the Arabic language properties in order to get the web more and more adapted to Arabic users. The proposed approach automatically clusters the web search results into high quality, and high significant clusters labels. The obtained clusters not only are coherent, but also can convey the contents to the users concisely and accurately. Therefore the Arabic users can decide at a glance whether the contents of a cluster are of interest.....
Fingerprints in Compressed Strings
Venue: arXiv cs.DS 2013
Year: 2013

The Karp-Rabin fingerprint of a string is a type of hash value that due to its strong properties has been used in many string algorithms. In this paper we show how to construct a data structure for a string $S$ of size $N$ compressed by a context-free grammar of size $n$ that answers fingerprint queries. That is, given indices $i$ and $j$, the answer to a query is the fingerprint of the substring $S[i,j]$. We present the first O(n) space data structures that answer fingerprint queries without decompressing any characters. For Straight Line Programs (SLP) we get $O(\log N)$ query time, and for Linear SLPs (an SLP derivative that captures LZ78 compression and its variations) we get $O(\log \log N)$ query time. Hence, our data structures has the same time and space complexity as for random access in SLPs. We utilize the fingerprint data structures to solve the longest common extension problem in query time $O(\log N \log \lce)$ and $O(\log \lce \log\log \lce + \log\log N)$ for SLPs and Linear SLPs, respectively. Here, $\lce$ denotes the length of the LCE.
HRF estimation improves sensitivity of fMRI encoding and decoding models
Venue: arXiv cs.LG 2013
Year: 2013

Extracting activation patterns from functional Magnetic Resonance Images (fMRI) datasets remains challenging in rapid-event designs due to the inherent delay of blood oxygen level-dependent (BOLD) signal. The general linear model (GLM) allows to estimate the activation from a design matrix and a fixed hemodynamic response function (HRF). However, the HRF is known to vary substantially between subjects and brain regions. In this paper, we propose a model for jointly estimating the hemodynamic response function (HRF) and the activation patterns via a low-rank representation of task effects.This model is based on the linearity assumption behind the GLM and can be computed using standard gradient-based solvers. We use the activation patterns computed by our model as input data for encoding and decoding studies and report performance improvement in both settings.
Quantization Noise Shaping for Information Maximizing ADCs
Venue: arXiv cs.IT 2013
Year: 2013

ADCs sit at the interface of the analog and digital worlds and fundamentally determine what information is available in the digital domain for processing. This paper shows that a configurable ADC can be designed for signals with non constant information as a function of frequency such that within a fixed power budget the ADC maximizes the information in the converted signal by frequency shaping the quantization noise. Quantization noise shaping can be realized via loop filter design for a single channel delta sigma ADC and extended to common time and frequency interleaved multi channel structures. Results are presented for example wireline and wireless style channels.
Image Optimization and Prediction
Venue: arXiv cs.CV 2013
Year: 2013

Image Processing, Optimization and Prediction of an Image play a key role in Computer Science. Image processing provides a way to analyze and identify an image .Many areas like medical image processing, Satellite images, natural images and artificial images requires lots of analysis and research on optimization. In Image Optimization and Prediction we are combining the features of Query Optimization, Image Processing and Prediction . Image optimization is used in Pattern analysis, object recognition, in medical Image processing to predict the type of diseases, in satellite images for predicting weather forecast, availability of water or mineral etc. Image Processing, Optimization and analysis is a wide open area for research .Lots of research has been conducted in the area of Image analysis and many techniques are available for image analysis but, a single technique is not yet identified for image analysis and prediction .our research is focused on identifying a global technique for image analysis and Prediction.
Performance Enhancement of Distributed Quasi Steady-State Genetic Algorithm
Venue: arXiv cs.NE 2013
Year: 2013

This paper proposes a new scheme for performance enhancement of distributed genetic algorithm (DGA). Initial population is divided in two classes i.e. female and male. Simple distance based clustering is used for cluster formation around females. For reclustering self-adaptive K-means is used, which produces well distributed and well separated clusters. The self-adaptive K-means used for reclustering automatically locates initial position of centroids and number of clusters. Four plans of co-evolution are applied on these clusters independently. Clusters evolve separately. Merging of clusters takes place depending on their performance. For experimentation unimodal and multimodal test functions have been used. Test result show that the new scheme of distribution of population has given better performance.
Test Model for Text Categorization and Text Summarization
Venue: arXiv cs.IR 2013
Year: 2013

Text Categorization is the task of automatically sorting a set of documents into categories from a predefined set and Text Summarization is a brief and accurate representation of input text such that the output covers the most important concepts of the source in a condensed manner. Document Summarization is an emerging technique for understanding the main purpose of any kind of documents. This paper presents a model that uses text categorization and text summarization for searching a document based on user query.
An Overview of Hindi Speech Recognition
Venue: arXiv cs.CL 2013
Year: 2013

In this age of information technology, information access in a convenient manner has gained importance. Since speech is a primary mode of communication among human beings, it is natural for people to expect to be able to carry out spoken dialogue with computer. Speech recognition system permits ordinary people to speak to the computer to retrieve information. It is desirable to have a human computer dialogue in local language. Hindi being the most widely spoken Language in India is the natural primary human language candidate for human machine interaction. There are five pairs of vowels in Hindi languages; one member is longer than the other one. This paper describes an overview of speech recognition system that includes how speech is produced and the properties and characteristics of Hindi Phoneme.
Verifying Fixed-Point Digital Filters using SMT-Based Bounded Model Checking
Venue: arXiv cs.SE 2013
Year: 2013

The implementation of digital filters in processors based on fixed-point arithmetic can lead to problems related to the finite word-length. In particular, the processing of signals in such filters can produce overflows and unwanted noise caused by quantization and round off effect during the accumulative addition and multiplication operations. In this paper, we describe a new approach to verify digital filters using an off-the-shelf bounded model checker called ESBMC, which supports full C/C++ and is based on satisfiability modulo theories solvers. In particular, we are able to verify the occurrence of overflows, limit cycles, and time constraints based on a discrete-time model implemented in C. The experiments show that the proposed approach can be used to verify potential problems in fixed-point implementation of digital filters and it can thus be effective in finding realistic design errors.
Scalable Audience Reach Estimation in Real-time Online Advertising
Venue: arXiv cs.LG 2013
Year: 2013

Online advertising has been introduced as one of the most efficient methods of advertising throughout the recent years. Yet, advertisers are concerned about the efficiency of their online advertising campaigns and consequently, would like to restrict their ad impressions to certain websites and/or certain groups of audience. These restrictions, known as targeting criteria, limit the reachability for better performance. This trade-off between reachability and performance illustrates a need for a forecasting system that can quickly predict/estimate (with good accuracy) this trade-off. Designing such a system is challenging due to (a) the huge amount of data to process, and, (b) the need for fast and accurate estimates. In this paper, we propose a distributed fault tolerant system that can generate such estimates fast with good accuracy. The main idea is to keep a small representative sample in memory across multiple machines and formulate the forecasting problem as queries against the sample. The key challenge is to find the best strata across the past data, perform multivariate stratified sampling while ensuring fuzzy fall-back to cover the small minorities. Our results show a significant improvement over the uniform and simple stratified sampling strategies which are currently widely used in the industry.
Using Feedback for Secrecy over Graphs
Venue: arXiv cs.IT 2013
Year: 2013

We study the problem of secure message multicasting over graphs in the presence of a passive (node) adversary who tries to eavesdrop in the network. We show that use of feedback, facilitated through the existence of cycles or undirected edges, enables higher rates than possible in directed acyclic graphs of the same mincut. We demonstrate this using code constructions for canonical combination networks (CCNs). We also provide general outer bounds as well as schemes for node adversaries over CCNs.
An efficient way to perform the assembly of finite element matrices in Matlab and Octave
Venue: arXiv cs.NA 2013
Year: 2013

We describe different optimization techniques to perform the assembly of finite element matrices in Matlab and Octave, from the standard approach to recent vectorized ones, without any low level language used. We finally obtain a simple and efficient vectorized algorithm able to compete in performance with dedicated software such as FreeFEM++. The principle of this assembly algorithm is general, we present it for different matrices in the P1 finite elements case and in linear elasticity. We present numerical results which illustrate the computational costs of the different approaches
Performance Analysis of Embarassingly Parallel Application on Cluster Computer Environment: A Case Study of Virtual Screening with Autodock Vina 1.1 on Hastinapura Cluster
Venue: arXiv cs.DC 2013
Year: 2013

IT based scientific research requires high computational resources. The limitation on funding and infrastructure led the high performance computing era from supercomputer to cluster and grid computing technology. Parallel application running well on cluster computer as well as supercomputer, one of the type is embarrassingly parallel application. Many scientist loves EP because it doesn't need any sophisticated technique but gives amazing performance. This paper discuss the bioinformatics research that used embarrassingly application and show its performance on cluster computer.
Discriminating Power of Centrality Measures
Venue: arXiv cs.SI 2013
Year: 2013

The calculation of centrality measures is common practice in the study of networks, as they attempt to quantify the importance of individual vertices, edges, or other components. Different centralities attempt to measure importance in different ways. In this paper, we examine a conjecture posed by E. Estrada regarding the ability of several measures to distinguish the vertices of networks. Estrada conjectured that if all vertices of a graph have the same subgraph centrality, then all vertices must also have the same degree, eigenvector, closeness, and betweenness centralities. We provide a counterexample for the latter two centrality measures and propose a revised conjecture.
Convergence of Distributed Randomized PageRank Algorithms
Venue: arXiv cs.SY 2013
Year: 2013

The PageRank algorithm employed by Google quantifies the importance of each page by the link structure of the web. To reduce the computational burden the distributed randomized PageRank algorithms (DRPA) recently appeared in literature suggest pages to update their ranking values by locally communicating with the linked pages. The main objective of the note is to show that the estimates generated by DRPA converge to the true PageRank value almost surely under the assumption that the randomization is realized in an independent and identically distributed (iid) way. This is achieved with the help of the stochastic approximation (SA) and its convergence results.
On the existence of 0/1 polytopes with high semidefinite extension complexity
Venue: arXiv cs.CC 2013
Year: 2013

In Rothvoß it was shown that there exists a 0/1 polytope (a polytope whose vertices are in \{0,1\}^{n}) such that any higher-dimensional polytope projecting to it must have 2^{Ω(n)} facets, i.e., its linear extension complexity is exponential. The question whether there exists a 0/1 polytope with high PSD extension complexity was left open. We answer this question in the affirmative by showing that there is a 0/1 polytope such that any spectrahedron projecting to it must be the intersection of a semidefinite cone of dimension~2^{Ω(n)} and an affine space. Our proof relies on a new technique to rescale semidefinite factorizations.
A Convex Analysis Approach to Computational Entropy
Venue: arXiv cs.IT 2013
Year: 2013

This paper studies the notion of computational entropy. Using techniques from convex optimization, we investigate the following problems: (a) Can we derandomize the computational entropy? More precisely, for the computational entropy, what is the real difference in security defined using the three important classes of circuits: deterministic boolean, deterministic real valued, or (the most powerful) randomized ones? (b) How large the difference in the computational entropy for an unbounded versus efficient adversary can be? (c) Can we obtain useful, simpler characterizations for the computational entropy?
Redundancy Allocation of Partitioned Linear Block Codes
Venue: arXiv cs.IT 2013
Year: 2013

Most memories suffer from both permanent defects and intermittent random errors. The partitioned linear block codes (PLBC) were proposed by Heegard to efficiently mask stuck-at defects and correct random errors. The PLBC have two separate redundancy parts for defects and random errors. In this paper, we investigate the allocation of redundancy between these two parts. The optimal redundancy allocation will be investigated using simulations and the simulation results show that the PLBC can significantly reduce the probability of decoding failure in memory with defects. In addition, we will derive the upper bound on the probability of decoding failure of PLBC and estimate the optimal redundancy allocation using this upper bound. The estimated redundancy allocation matches the optimal redundancy allocation well.
Riding the crest of the altmetrics wave: How librarians can help prepare faculty for the next generation of research impact metrics
Venue: arXiv cs.DL 2013
Year: 2013

As scholars migrate into online spaces like Mendeley, blogs, Twitter, and more, they leave new traces of once-invisible interactions like reading, saving, discussing, and recommending. Observing these traces can inform new metrics of scholarly influence and impact -- so-called "altmetrics." Stakeholders in academia are beginning to discuss how and where altmetrics can be useful towards evaluating a researcher's academic contribution. As this interest grows, libraries are in a unique position to help support an informed dialog on campus. We suggest that librarians can provide this support in three main ways: informing emerging conversations with the latest research, supporting experimentation with emerging altmetrics tools, and engaging in early altmetrics education and outreach. We include examples and lists of resources to help librarians fill these roles.
Symmetry in Distributed Storage Systems
Venue: arXiv cs.IT 2013
Year: 2013

The max-flow outer bound is achievable by regenerating codes for functional repair distributed storage system. However, the capacity of exact repair distributed storage system is an open problem. In this paper, the linear programming bound for exact repair distributed storage systems is formulated. A notion of symmetrical sets for a set of random variables is given and equalities of joint entropies for certain subsets of random variables in a symmetrical set is established. Concatenation coding scheme for exact repair distributed storage systems is proposed and it is shown that concatenation coding scheme is sufficient to achieve any admissible rate for any exact repair distributed storage system. Equalities of certain joint entropies of random variables induced by concatenation scheme is shown. These equalities of joint entropies are new tools to simplify the linear programming bound and to obtain stronger converse results for exact repair distributed storage systems.
Exhaustive Search for Small Dimension Recursive MDS Diffusion Layers for Block Ciphers and Hash Functions
Venue: arXiv cs.CR 2013
Year: 2013

This article presents a new algorithm to find MDS matrices that are well suited for use as a diffusion layer in lightweight block ciphers. Using an recursive construction, it is possible to obtain matrices with a very compact description. Classical field multiplications can also be replaced by simple F2-linear transformations (combinations of XORs and shifts) which are much lighter. Using this algorithm, it was possible to design a 16x16 matrix on a 5-bit alphabet, yielding an efficient 80-bit diffusion layer with maximal branch number.
Stationary analysis of the Shortest Queue First service policy
Venue: arXiv cs.PF 2013
Year: 2013

We analyze the so-called Shortest Queue First (SQF) queueing discipline whereby a unique server addresses queues in parallel by serving at any time that queue with the smallest workload. Considering a stationary system composed of two parallel queues and assuming Poisson arrivals and general service time distributions, we first establish the functional equations satisfied by the Laplace transforms of the workloads in each queue. We further specialize these equations to the so-called "symmetric case", with same arrival rates and identical exponential service time distributions at each queue; we then obtain a functional equation $$ M(z) = q(z) \cdot M \circ h(z) + L(z) $$ for unknown function $M$, where given functions $q$, $L$ and $h$ are related to one branch of a cubic polynomial equation. We study the analyticity domain of function $M$ and express it by a series expansion involving all iterates of function $h$. This allows us to determine empty queue probabilities along with the tail of the workload distribution in each queue. This tail appears to be identical to that of the Head-of-Line preemptive priority system, which is the key feature desired for the SQF discipline.