pwc-archive/papers-with-abstracts huggingface dataset:
Square Deal: Lower Bounds and Improved Relaxations for Tensor Recovery
Authors: Cun Mu, Bo Huang, John Wright, Donald Goldfarb
Date: 2013-07-22 00:00:00

Recovering a low-rank tensor from incomplete information is a recurring
problem in signal processing and machine learning. The most popular convex
relaxation of this problem minimizes the sum of the nuclear norms of the
unfoldings of the tensor. We show that this approach can be substantially
suboptimal: reliably recovering a $K$-way tensor of length $n$ and Tucker rank
$r$ from Gaussian measurements requires $\Omega(r n^{K-1})$ observations. In
contrast, a certain (intractable) nonconvex formulation needs only $O(r^K +
nrK)$ observations. We introduce a very simple, new convex relaxation, which
partially bridges this gap. Our new formulation succeeds with $O(r^{\lfloor K/2
\rfloor}n^{\lceil K/2 \rceil})$ observations. While these results pertain to
Gaussian measurements, simulations strongly suggest that the new norm also
outperforms the sum of nuclear norms for tensor completion from a random subset
of entries.
  Our lower bound for the sum-of-nuclear-norms model follows from a new result
on recovering signals with multiple sparse structures (e.g. sparse, low rank),
which perhaps surprisingly demonstrates the significant suboptimality of the
commonly used recovery approach via minimizing the sum of individual sparsity
inducing norms (e.g. $l_1$, nuclear norm). Our new formulation for low-rank
tensor recovery however opens the possibility in reducing the sample complexity
by exploiting several structures jointly.
Search-Space Characterization for Real-time Heuristic Search
Authors: Daniel Huntley, Vadim Bulitko
Date: 2013-08-15 00:00:00
Tasks: Heuristic Search

Recent real-time heuristic search algorithms have demonstrated outstanding
performance in video-game pathfinding. However, their applications have been
thus far limited to that domain. We proceed with the aim of facilitating wider
applications of real-time search by fostering a greater understanding of the
performance of recent algorithms. We first introduce eight
algorithm-independent complexity measures for search spaces and correlate their
values with algorithm performance. The complexity measures are statistically
shown to be significant predictors of algorithm performance across a set of
commercial video-game maps. We then extend this analysis to a wider variety of
search spaces in the first application of database-driven real-time search to
domains outside of video-game pathfinding. In doing so, we gain insight into
algorithm performance and possible enhancement as well as into search space
complexity.
A Secure and Comparable Text Encryption Algorithm
Authors: Nicholas Kersting
Date: 2013-08-15 00:00:00
Tasks: Semantic Similarity, Semantic Textual Similarity

This paper discloses a simple algorithm for encrypting text messages, based
on the NP-completeness of the subset sum problem, such that the similarity
between encryptions is roughly proportional to the semantic similarity between
their generating messages. This allows parties to compare encrypted messages
for semantic overlap without trusting an intermediary and might be applied, for
example, as a means of finding scientific collaborators over the Internet.
Impulse Noise Removal In Speech Using Wavelets
Authors: R. C. Nongpiur
Date: 2013-08-14 00:00:00

A new method for removing impulse noise from speech in the wavelet transform
domain is proposed. The method utilizes the multiresolution property of the
wavelet transform, which provides finer time resolution at the higher
frequencies than the short-time Fourier transform (STFT), to effectively
identify and remove impulse noise. It uses two features of speech to
discriminate speech from impulse noise: one is the slow time-varying nature of
speech and the other is the Lipschitz regularity of the speech components. On
the basis of these features, an algorithm has been developed to identify and
suppress wavelet coefficients that correspond to impulse noise. Experiment
results show that the new method is able to significantly reduce impulse noise
without degrading the quality of the speech signal or introducing any audible
artifacts.
Equitability Analysis of the Maximal Information Coefficient, with Comparisons
Authors: David Reshef, Yakir Reshef, Michael Mitzenmacher, Pardis Sabeti
Date: 2013-01-27 00:00:00
Tasks: Mutual Information Estimation

A measure of dependence is said to be equitable if it gives similar scores to
equally noisy relationships of different types. Equitability is important in
data exploration when the goal is to identify a relatively small set of
strongest associations within a dataset as opposed to finding as many non-zero
associations as possible, which often are too many to sift through. Thus an
equitable statistic, such as the maximal information coefficient (MIC), can be
useful for analyzing high-dimensional data sets. Here, we explore both
equitability and the properties of MIC, and discuss several aspects of the
theory and practice of MIC. We begin by presenting an intuition behind the
equitability of MIC through the exploration of the maximization and
normalization steps in its definition. We then examine the speed and optimality
of the approximation algorithm used to compute MIC, and suggest some directions
for improving both. Finally, we demonstrate in a range of noise models and
sample sizes that MIC is more equitable than natural alternatives, such as
mutual information estimation and distance correlation.
Arabic Text Recognition in Video Sequences
Authors: M. Ben Halima, H. Karray, A. M. Alimi
Date: 2013-08-14 00:00:00

In this paper, we propose a robust approach for text extraction and
recognition from Arabic news video sequence. The text included in video
sequences is an important needful for indexing and searching system. However,
this text is difficult to detect and recognize because of the variability of
its size, their low resolution characters and the complexity of the
backgrounds. To solve these problems, we propose a system performing in two
main tasks: extraction and recognition of text. Our system is tested on a
varied database composed of different Arabic news programs and the obtained
results are encouraging and show the merits of our approach.
An interactive engine for multilingual video browsing using semantic content
Authors: M. Ben Halima, M. Hamroun, S. Ben Moussa, A. M. Alimi
Date: 2013-08-14 00:00:00
Tasks: Retrieval

The amount of audio-visual information has increased dramatically with the
advent of High Speed Internet. Furthermore, technological advances in recent
years in the field of information technology, have simplified the use of video
data in various fields by the general public. This made it possible to store
large collections of video documents into computer systems. To enable efficient
use of these collections, it is necessary to develop tools to facilitate access
to these documents and handling them. In this paper we propose a method for
indexing and retrieval of video sequences in a video database of large
dimension, based on a weighting technique to calculate the degree of membership
of a concept in a video also a structuring of the data of the audio-visual
(context / concept / video) and a relevance feedback mechanism.
Guiding Designs of Self-Organizing Swarms: Interactive and Automated Approaches
Authors: Hiroki Sayama
Date: 2013-08-14 00:00:00

Self-organization of heterogeneous particle swarms is rich in its dynamics
but hard to design in a traditional top-down manner, especially when many types
of kinetically distinct particles are involved. In this chapter, we discuss how
we have been addressing this problem by (1) utilizing and enhancing interactive
evolutionary design methods and (2) realizing spontaneous evolution of self
organizing swarms within an artificial ecosystem.
Normalized Google Distance of Multisets with Applications
Authors: Andrew R. Cohen, P. M. B. Vitanyi
Date: 2013-08-14 00:00:00

Normalized Google distance (NGD) is a relative semantic distance based on the
World Wide Web (or any other large electronic database, for instance Wikipedia)
and a search engine that returns aggregate page counts. The earlier NGD between
pairs of search terms (including phrases) is not sufficient for all
applications. We propose an NGD of finite multisets of search terms that is
better for many applications. This gives a relative semantics shared by a
multiset of search terms. We give applications and compare the results with
those obtained using the pairwise NGD. The derivation of NGD method is based on
Kolmogorov complexity.
Locally epistatic genomic relationship matrices for genomic association, prediction and selection
Authors: Deniz Akdemir
Date: 2013-02-14 00:00:00

As the amount and complexity of genetic information increases it is necessary
that we explore some efficient ways of handling these data. This study takes
the "divide and conquer" approach for analyzing high dimensional genomic data.
Our aims include reducing the dimensionality of the problem that has to be
dealt one at a time, improving the performance and interpretability of the
models. We propose using the inherent structures in the genome; to divide the
bigger problem into manageable parts. In plant and animal breeding studies a
distinction is made between the commercial value (additive + epistatic genetic
effects) and the breeding value (additive genetic effects) of an individual
since it is expected that some of the epistatic genetic effects will be lost
due to recombination. In this paper, we argue that the breeder can take
advantage of some of the epistatic marker effects in regions of low
recombination. The models introduced here aim to estimate local epistatic line
heritability by using the genetic map information and combine the local
additive and epistatic effects. To this end, we have used semi-parametric mixed
models with multiple local genomic relationship matrices with hierarchical
testing designs and lasso post-processing for sparsity in the final model and
speed. Our models produce good predictive performance along with genetic
association information.
System and Methods for Converting Speech to SQL
Authors: Sachin Kumar, Ashish Kumar, Pinaki Mitra, Girish Sundaram
Date: 2013-08-14 00:00:00
Tasks: Translation

This paper concerns with the conversion of a Spoken English Language Query
into SQL for retrieving data from RDBMS. A User submits a query as speech
signal through the user interface and gets the result of the query in the text
format. We have developed the acoustic and language models using which a speech
utterance can be converted into English text query and thus natural language
processing techniques can be applied on this English text query to generate an
equivalent SQL query. For conversion of speech into English text HTK and Julius
tools have been used and for conversion of English text query into SQL query we
have implemented a System which uses rule based translation to translate
English Language Query into SQL Query. The translation uses lexical analyzer,
parser and syntax directed translation techniques like in compilers. JFLex and
BYACC tools have been used to build lexical analyzer and parser respectively.
System is domain independent i.e. system can run on different database as it
generates lex files from the underlying database.
When are Overcomplete Topic Models Identifiable? Uniqueness of Tensor Tucker Decompositions with Structured Sparsity
Authors: Animashree Anandkumar, Daniel Hsu, Majid Janzamin, Sham Kakade
Date: 2013-08-13 00:00:00
Proceeding: NeurIPS 2013 12
Tasks: Topic Models

Overcomplete latent representations have been very popular for unsupervised
feature learning in recent years. In this paper, we specify which overcomplete
models can be identified given observable moments of a certain order. We
consider probabilistic admixture or topic models in the overcomplete regime,
where the number of latent topics can greatly exceed the size of the observed
word vocabulary. While general overcomplete topic models are not identifiable,
we establish generic identifiability under a constraint, referred to as topic
persistence. Our sufficient conditions for identifiability involve a novel set
of "higher order" expansion conditions on the topic-word matrix or the
population structure of the model. This set of higher-order expansion
conditions allow for overcomplete models, and require the existence of a
perfect matching from latent topics to higher order observed words. We
establish that random structured topic models are identifiable w.h.p. in the
overcomplete regime. Our identifiability results allows for general
(non-degenerate) distributions for modeling the topic proportions, and thus, we
can handle arbitrarily correlated topics in our framework. Our identifiability
results imply uniqueness of a class of tensor decompositions with structured
sparsity which is contained in the class of Tucker decompositions, but is more
general than the Candecomp/Parafac (CP) decomposition.
Universally consistent vertex classification for latent positions graphs
Authors: Minh Tang, Daniel L. Sussman, Carey E. Priebe
Date: 2012-12-05 00:00:00
Tasks: Classification, General Classification, Position

In this work we show that, using the eigen-decomposition of the adjacency
matrix, we can consistently estimate feature maps for latent position graphs
with positive definite link function $\kappa$, provided that the latent
positions are i.i.d. from some distribution F. We then consider the
exploitation task of vertex classification where the link function $\kappa$
belongs to the class of universal kernels and class labels are observed for a
number of vertices tending to infinity and that the remaining vertices are to
be classified. We show that minimization of the empirical $\varphi$-risk for
some convex surrogate $\varphi$ of 0-1 loss over a class of linear classifiers
with increasing complexities yields a universally consistent classifier, that
is, a classification rule with error converging to Bayes optimal for any
distribution F.
Extended Distributed Learning Automata:A New Method for Solving Stochastic Graph Optimization Problems
Authors: M. R. Mollakhalili Meybodi, M. R. Meybodi
Date: 2013-08-13 00:00:00

In this paper, a new structure of cooperative learning automata so-called
extended learning automata (eDLA) is introduced. Based on the proposed
structure, a new iterative randomized heuristic algorithm for finding optimal
sub-graph in a stochastic edge-weighted graph through sampling is proposed. It
has been shown that the proposed algorithm based on new networked-structure can
be to solve the optimization problems on stochastic graph through less number
of sampling in compare to standard sampling. Stochastic graphs are graphs in
which the edges have an unknown distribution probability weights. Proposed
algorithm uses an eDLA to find a policy that leads to an induced sub-graph that
satisfies some restrictions such as minimum or maximum weight (length). At each
stage of the proposed algorithm, eDLA determines which edges to be sampled.
This eDLA-based proposed sampling method may result in decreasing unnecessary
samples and hence decreasing the time that algorithm requires for finding the
optimal sub-graph. It has been shown that proposed method converge to optimal
solution, furthermore the probability of this convergence can be made
arbitrarily close to 1 by using a sufficiently small learning rate. A new
variance-aware threshold value was proposed that can be improving significantly
convergence rate of the proposed eDLA-based algorithm. It has been shown that
the proposed algorithm is competitive in terms of the quality of the solution
An efficient ant based qos aware intelligent temporally ordered routing algorithm for manets
Authors: Debajit Sensarma, Koushik Majumder
Date: 2013-08-13 00:00:00

A Mobile Ad hoc network (MANET) is a self configurable network connected by
wireless links. This type of network is only suitable for temporary
communication links as it is infrastructure-less and there is no centralised
control. Providing QoS aware routing is a challenging task in this type of
network due to dynamic topology and limited resources. The main purpose of QoS
aware routing is to find a feasible path from source to destination which will
satisfy two or more end to end QoS constrains. Therefore, the task of designing
an efficient routing algorithm which will satisfy all the quality of service
requirements and be robust and adaptive is considered as a highly challenging
problem. In this work we have designed a new efficient and energy aware
multipath routing algorithm based on ACO framework, inspired by the behaviours
of biological ants. Basically by considering QoS constraints and artificial
ants we have designed an intelligent version of classical Temporally Ordered
Routing Algorithm (TORA) which will increase network lifetime and decrease
packet loss and average end to end delay that makes this algorithm suitable for
real time and multimedia applications.
A New Fuzzy Stacked Generalization Technique and Analysis of its Performance
Authors: Mete Ozay, Fatos T. Yarman Vural
Date: 2012-04-01 00:00:00
Tasks: Attribute, Ensemble Learning, General Classification

In this study, a new Stacked Generalization technique called Fuzzy Stacked
Generalization (FSG) is proposed to minimize the difference between N -sample
and large-sample classification error of the Nearest Neighbor classifier. The
proposed FSG employs a new hierarchical distance learning strategy to minimize
the error difference. For this purpose, we first construct an ensemble of
base-layer fuzzy k- Nearest Neighbor (k-NN) classifiers, each of which receives
a different feature set extracted from the same sample set. The fuzzy
membership values computed at the decision space of each fuzzy k-NN classifier
are concatenated to form the feature vectors of a fusion space. Finally, the
feature vectors are fed to a meta-layer classifier to learn the degree of
accuracy of the decisions of the base-layer classifiers for meta-layer
classification. Rather than the power of the individual base layer-classifiers,
diversity and cooperation of the classifiers become an important issue to
improve the overall performance of the proposed FSG. A weak base-layer
classifier may boost the overall performance more than a strong classifier, if
it is capable of recognizing the samples, which are not recognized by the rest
of the classifiers, in its own feature space. The experiments explore the type
of the collaboration among the individual classifiers required for an improved
performance of the suggested architecture. Experiments on multiple feature
real-world datasets show that the proposed FSG performs better than the state
of the art ensemble learning algorithms such as Adaboost, Random Subspace and
Rotation Forest. On the other hand, compatible performances are observed in the
experiments on single feature multi-attribute datasets.
B(eo)W(u)LF: Facilitating recurrence analysis on multi-level language
Authors: A. Paxton, R. Dale
Date: 2013-08-12 00:00:00
Tasks: Form

Discourse analysis may seek to characterize not only the overall composition
of a given text but also the dynamic patterns within the data. This technical
report introduces a data format intended to facilitate multi-level
investigations, which we call the by-word long-form or B(eo)W(u)LF. Inspired by
the long-form data format required for mixed-effects modeling, B(eo)W(u)LF
structures linguistic data into an expanded matrix encoding any number of
researchers-specified markers, making it ideal for recurrence-based analyses.
While we do not necessarily claim to be the first to use methods along these
lines, we have created a series of tools utilizing Python and MATLAB to enable
such discourse analyses and demonstrate them using 319 lines of the Old English
epic poem, Beowulf, translated into modern English.
Local image registration a comparison for bilateral registration mammography
Authors: José M. Celaya-Padilla, Juan Rodriguez-Rojas, Victor Trevino, José G. Gerardo Tamez-Pena
Date: 2013-08-12 00:00:00
Tasks: Image Registration

Early tumor detection is key in reducing the number of breast cancer death
and screening mammography is one of the most widely available and reliable
method for early detection. However, it is difficult for the radiologist to
process with the same attention each case, due the large amount of images to be
read. Computer aided detection (CADe) systems improve tumor detection rate; but
the current efficiency of these systems is not yet adequate and the correct
interpretation of CADe outputs requires expert human intervention. Computer
aided diagnosis systems (CADx) are being designed to improve cancer diagnosis
accuracy, but they have not been efficiently applied in breast cancer. CADx
efficiency can be enhanced by considering the natural mirror symmetry between
the right and left breast. The objective of this work is to evaluate
co-registration algorithms for the accurate alignment of the left to right
breast for CADx enhancement. A set of mammograms were artificially altered to
create a ground truth set to evaluate the registration efficiency of DEMONs,
and SPLINE deformable registration algorithms. The registration accuracy was
evaluated using mean square errors, mutual information and correlation. The
results on the 132 images proved that the SPLINE deformable registration
over-perform the DEMONS on mammography images.
Faster gradient descent and the efficient recovery of images
Authors: Hui Huang, Uri Ascher
Date: 2013-08-12 00:00:00
Tasks: Deblurring, Denoising, Image Deblurring

Much recent attention has been devoted to gradient descent algorithms where
the steepest descent step size is replaced by a similar one from a previous
iteration or gets updated only once every second step, thus forming a {\em
faster gradient descent method}. For unconstrained convex quadratic
optimization these methods can converge much faster than steepest descent. But
the context of interest here is application to certain ill-posed inverse
problems, where the steepest descent method is known to have a smoothing,
regularizing effect, and where a strict optimization solution is not necessary.
  Specifically, in this paper we examine the effect of replacing steepest
descent by a faster gradient descent algorithm in the practical context of
image deblurring and denoising tasks. We also propose several highly efficient
schemes for carrying out these tasks independently of the step size selection,
as well as a scheme for the case where both blur and significant noise are
present.
  In the above context there are situations where many steepest descent steps
are required, thus building slowness into the solution procedure. Our general
conclusion regarding gradient descent methods is that in such cases the faster
gradient descent methods offer substantial advantages. In other situations
where no such slowness buildup arises the steepest descent method can still be
very effective.