pwc-archive/papers-with-abstracts huggingface dataset:
Comparison of Algorithms for Compressed Sensing of Magnetic Resonance Images
Authors: Jelena Badnjar
Date: 2015-02-07 00:00:00
Tasks: compressed sensing, Compressive Sensing

Magnetic resonance imaging (MRI) is an essential medical tool with inherently
slow data acquisition process. Slow acquisition process requires patient to be
long time exposed to scanning apparatus. In recent years significant efforts
are made towards the applying Compressive Sensing technique to the acquisition
process of MRI and biomedical images. Compressive Sensing is an emerging theory
in signal processing. It aims to reduce the amount of acquired data required
for successful signal reconstruction. Reducing the amount of acquired image
coefficients leads to lower acquisition time, i.e. time of exposition to the
MRI apparatus. Using optimization algorithms, satisfactory image quality can be
obtained from the small set of acquired samples. A number of optimization
algorithms for the reconstruction of the biomedical images is proposed in the
literature. In this paper, three commonly used optimization algorithms are
compared and results are presented on the several MRI images.
Complexity and universality in the long-range order of words
Authors: Marcelo A Montemurro, Damián H. Zanette
Date: 2015-03-03 00:00:00

As is the case of many signals produced by complex systems, language presents
a statistical structure that is balanced between order and disorder. Here we
review and extend recent results from quantitative characterisations of the
degree of order in linguistic sequences that give insights into two relevant
aspects of language: the presence of statistical universals in word ordering,
and the link between semantic information and the statistical linguistic
structure. We first analyse a measure of relative entropy that assesses how
much the ordering of words contributes to the overall statistical structure of
language. This measure presents an almost constant value close to 3.5 bits/word
across several linguistic families. Then, we show that a direct application of
information theory leads to an entropy measure that can quantify and extract
semantic structures from linguistic samples, even without prior knowledge of
the underlying language.
Short Term Memory Capacity in Networks via the Restricted Isometry Property
Authors: Adam S. Charles, Han Lun Yap, Christopher J. Rozell
Date: 2013-07-01 00:00:00
Tasks: compressed sensing

Cortical networks are hypothesized to rely on transient network activity to
support short term memory (STM). In this paper we study the capacity of
randomly connected recurrent linear networks for performing STM when the input
signals are approximately sparse in some basis. We leverage results from
compressed sensing to provide rigorous non asymptotic recovery guarantees,
quantifying the impact of the input sparsity level, the input sparsity basis,
and the network characteristics on the system capacity. Our analysis
demonstrates that network memory capacities can scale superlinearly with the
number of nodes, and in some situations can achieve STM capacities that are
much larger than the network size. We provide perfect recovery guarantees for
finite sequences and recovery bounds for infinite sequences. The latter
analysis predicts that network STM systems may have an optimal recovery length
that balances errors due to omission and recall mistakes. Furthermore, we show
that the conditions yielding optimal STM capacity can be embodied in several
network topologies, including networks with sparse or dense connectivities.
Using Descriptive Video Services to Create a Large Data Source for Video Annotation Research
Authors: Atousa Torabi, Christopher Pal, Hugo Larochelle, Aaron Courville
Date: 2015-03-03 00:00:00
Tasks: Descriptive, Video Description

In this work, we introduce a dataset of video annotated with high quality
natural language phrases describing the visual content in a given segment of
time. Our dataset is based on the Descriptive Video Service (DVS) that is now
encoded on many digital media products such as DVDs. DVS is an audio narration
describing the visual elements and actions in a movie for the visually
impaired. It is temporally aligned with the movie and mixed with the original
movie soundtrack. We describe an automatic DVS segmentation and alignment
method for movies, that enables us to scale up the collection of a DVS-derived
dataset with minimal human intervention. Using this method, we have collected
the largest DVS-derived dataset for video description of which we are aware.
Our dataset currently includes over 84.6 hours of paired video/sentences from
92 DVDs and is growing.
Kernel Interpolation for Scalable Structured Gaussian Processes (KISS-GP)
Authors: Andrew Gordon Wilson, Hannes Nickisch
Date: 2015-03-03 00:00:00
Tasks: Gaussian Processes

We introduce a new structured kernel interpolation (SKI) framework, which
generalises and unifies inducing point methods for scalable Gaussian processes
(GPs). SKI methods produce kernel approximations for fast computations through
kernel interpolation. The SKI framework clarifies how the quality of an
inducing point approach depends on the number of inducing (aka interpolation)
points, interpolation strategy, and GP covariance kernel. SKI also provides a
mechanism to create new scalable kernel methods, through choosing different
kernel interpolation strategies. Using SKI, with local cubic kernel
interpolation, we introduce KISS-GP, which is 1) more scalable than inducing
point alternatives, 2) naturally enables Kronecker and Toeplitz algebra for
substantial additional gains in scalability, without requiring any grid data,
and 3) can be used for fast and expressive kernel learning. KISS-GP costs O(n)
time and storage for GP inference. We evaluate KISS-GP for kernel matrix
approximation, kernel learning, and natural sound modelling.
Combining Probabilistic, Causal, and Normative Reasoning in CP-logic
Authors: Sander Beckers, Joost Vennekens
Date: 2015-03-03 00:00:00
Tasks: Ethics

In recent years the search for a proper formal definition of actual causation
-- i.e., the relation of cause-effect as it is instantiated in specific
observations, rather than general causal relations -- has taken on impressive
proportions. In part this is due to the insight that this concept plays a
fundamental role in many different fields, such as legal theory, engineering,
medicine, ethics, etc. Because of this diversity in applications, some
researchers have shifted focus from a single idealized definition towards a
more pragmatic, context-based account. For instance, recent work by Halpern and
Hitchcock draws on empirical research regarding people's causal judgments, to
suggest a graded and context-sensitive notion of causation. Although we
sympathize with many of their observations, their restriction to a merely
qualitative ordering runs into trouble for more complex examples. Therefore we
aim to improve on their approach, by using the formal language of CP-logic
(Causal Probabilistic logic), and the framework for defining actual causation
that was developed by the current authors using it. First we rephrase their
ideas into our quantitative, probabilistic setting, after which we modify it to
accommodate a greater class of examples. Further, we introduce a formal
distinction between statistical and normative considerations.
Projection onto the capped simplex
Authors: Weiran Wang, Canyi Lu
Date: 2015-03-03 00:00:00

We provide a simple and efficient algorithm for computing the Euclidean
projection of a point onto the capped simplex---a simplex with an additional
uniform bound on each coordinate---together with an elementary proof. Both the
MATLAB and C++ implementations of the proposed algorithm can be downloaded at
https://eng.ucmerced.edu/people/wwang5.
Anisotropic Diffusion in ITK
Authors: Jean-Marie Mirebeau, Jérôme Fehrenbach, Laurent Risser, Shaza Tobji
Date: 2015-03-03 00:00:00

Anisotropic Non-Linear Diffusion is a powerful image processing technique,
which allows to simultaneously remove the noise and enhance sharp features in
two or three dimensional images. Anisotropic Diffusion is understood here in
the sense of Weickert, meaning that diffusion tensors are anisotropic and
reflect the local orientation of image features. This is in contrast with the
non-linear diffusion filter of Perona and Malik, which only involves scalar
diffusion coefficients, in other words isotropic diffusion tensors. In this
paper, we present an anisotropic non-linear diffusion technique we implemented
in ITK. This technique is based on a recent adaptive scheme making the
diffusion stable and requiring limited numerical resources. (See supplementary
data.)
On memetic search for the max-mean dispersion problem
Authors: Xiangjing Lai, Jin-Kao Hao
Date: 2015-03-03 00:00:00

Given a set $V$ of $n$ elements and a distance matrix $[d_{ij}]_{n\times n}$
among elements, the max-mean dispersion problem (MaxMeanDP) consists in
selecting a subset $M$ from $V$ such that the mean dispersion (or distance)
among the selected elements is maximized. Being a useful model to formulate
several relevant applications, MaxMeanDP is known to be NP-hard and thus
computationally difficult. In this paper, we present a highly effective memetic
algorithm for MaxMeanDP which relies on solution recombination and local
optimization to find high quality solutions. Computational experiments on the
set of 160 benchmark instances with up to 1000 elements commonly used in the
literature show that the proposed algorithm improves or matches the published
best known results for all instances in a short computing time, with only one
exception, while achieving a high success rate of 100\%. In particular, we
improve 59 previous best results out of the 60 most challenging instances.
Results on a set of 40 new large instances with 3000 and 5000 elements are also
presented. The key ingredients of the proposed algorithm are investigated to
shed light on how they affect the performance of the algorithm.
A totally unimodular view of structured sparsity
Authors: Marwa El Halabi, Volkan Cevher
Date: 2014-11-07 00:00:00

This paper describes a simple framework for structured sparse recovery based
on convex optimization. We show that many structured sparsity models can be
naturally represented by linear matrix inequalities on the support of the
unknown parameters, where the constraint matrix has a totally unimodular (TU)
structure. For such structured models, tight convex relaxations can be obtained
in polynomial time via linear programming. Our modeling framework unifies the
prevalent structured sparsity norms in the literature, introduces new
interesting ones, and renders their tightness and tractability arguments
transparent.
Normalization based K means Clustering Algorithm
Authors: Deepali Virmani, Shweta Taneja, Geetika Malhotra
Date: 2015-03-03 00:00:00
Tasks: Clustering

K-means is an effective clustering technique used to separate similar data
into groups based on initial centroids of clusters. In this paper,
Normalization based K-means clustering algorithm(N-K means) is proposed.
Proposed N-K means clustering algorithm applies normalization prior to
clustering on the available data as well as the proposed approach calculates
initial centroids based on weights. Experimental results prove the betterment
of proposed N-K means clustering algorithm over existing K-means clustering
algorithm in terms of complexity and overall performance.
An Ant Colony Optimization Algorithm for Partitioning Graphs with Supply and Demand
Authors: Raka Jovanovic, Milan Tuba, Stefan Voss
Date: 2015-03-03 00:00:00

In this paper we focus on finding high quality solutions for the problem of
maximum partitioning of graphs with supply and demand (MPGSD). There is a
growing interest for the MPGSD due to its close connection to problems
appearing in the field of electrical distribution systems, especially for the
optimization of self-adequacy of interconnected microgrids. We propose an ant
colony optimization algorithm for the problem. With the goal of further
improving the algorithm we combine it with a previously developed correction
procedure. In our computational experiments we evaluate the performance of the
proposed algorithm on both trees and general graphs. The tests show that the
method manages to find optimal solutions in more than 50% of the problem
instances, and has an average relative error of less than 0.5% when compared to
known optimal solutions.
A Primal-Dual Algorithmic Framework for Constrained Convex Minimization
Authors: Quoc Tran-Dinh, Volkan Cevher
Date: 2014-06-20 00:00:00

We present a primal-dual algorithmic framework to obtain approximate
solutions to a prototypical constrained convex optimization problem, and
rigorously characterize how common structural assumptions affect the numerical
efficiency. Our main analysis technique provides a fresh perspective on
Nesterov's excessive gap technique in a structured fashion and unifies it with
smoothing and primal-dual methods. For instance, through the choices of a dual
smoothing strategy and a center point, our framework subsumes decomposition
algorithms, augmented Lagrangian as well as the alternating direction
method-of-multipliers methods as its special cases, and provides optimal
convergence rates on the primal objective residual as well as the primal
feasibility gap of the iterates for all.
Self-Dictionary Sparse Regression for Hyperspectral Unmixing: Greedy Pursuit and Pure Pixel Search are Related
Authors: Xiao Fu, Wing-Kin Ma, Tsung-Han Chan, José M. Bioucas-Dias
Date: 2014-09-15 00:00:00
Tasks: Hyperspectral Unmixing, regression, Single Particle Analysis

This paper considers a recently emerged hyperspectral unmixing formulation
based on sparse regression of a self-dictionary multiple measurement vector
(SD-MMV) model, wherein the measured hyperspectral pixels are used as the
dictionary. Operating under the pure pixel assumption, this SD-MMV formalism is
special in that it allows simultaneous identification of the endmember spectral
signatures and the number of endmembers. Previous SD-MMV studies mainly focus
on convex relaxations. In this study, we explore the alternative of greedy
pursuit, which generally provides efficient and simple algorithms. In
particular, we design a greedy SD-MMV algorithm using simultaneous orthogonal
matching pursuit. Intriguingly, the proposed greedy algorithm is shown to be
closely related to some existing pure pixel search algorithms, especially, the
successive projection algorithm (SPA). Thus, a link between SD-MMV and pure
pixel search is revealed. We then perform exact recovery analyses, and prove
that the proposed greedy algorithm is robust to noise---including its
identification of the (unknown) number of endmembers---under a sufficiently low
noise level. The identification performance of the proposed greedy algorithm is
demonstrated through both synthetic and real-data experiments.
A Survey On Video Forgery Detection
Authors: Sowmya K. N., H. R. Chennamma
Date: 2015-03-03 00:00:00
Tasks: Survey

The Digital Forgeries though not visibly identifiable to human perception it
may alter or meddle with underlying natural statistics of digital content.
Tampering involves fiddling with video content in order to cause damage or make
unauthorized alteration/modification. Tampering detection in video is
cumbersome compared to image when considering the properties of the video.
Tampering impacts need to be studied and the applied technique/method is used
to establish the factual information for legal course in judiciary. In this
paper we give an overview of the prior literature and challenges involved in
video forgery detection where passive approach is found.
Robustly Leveraging Prior Knowledge in Text Classification
Authors: Biao Liu, Minlie Huang
Date: 2015-03-03 00:00:00
Tasks: Classification, General Classification, text-classification, Text Classification

Prior knowledge has been shown very useful to address many natural language
processing tasks. Many approaches have been proposed to formalise a variety of
knowledge, however, whether the proposed approach is robust or sensitive to the
knowledge supplied to the model has rarely been discussed. In this paper, we
propose three regularization terms on top of generalized expectation criteria,
and conduct extensive experiments to justify the robustness of the proposed
methods. Experimental results demonstrate that our proposed methods obtain
remarkable improvements and are much more robust than baselines.
Transductive Multi-view Zero-Shot Learning
Authors: Yanwei Fu, Timothy M. Hospedales, Tao Xiang, Shaogang Gong
Date: 2015-01-19 00:00:00
Tasks: Transfer Learning, Zero-Shot Learning

Most existing zero-shot learning approaches exploit transfer learning via an
intermediate-level semantic representation shared between an annotated
auxiliary dataset and a target dataset with different classes and no
annotation. A projection from a low-level feature space to the semantic
representation space is learned from the auxiliary dataset and is applied
without adaptation to the target dataset. In this paper we identify two
inherent limitations with these approaches. First, due to having disjoint and
potentially unrelated classes, the projection functions learned from the
auxiliary dataset/domain are biased when applied directly to the target
dataset/domain. We call this problem the projection domain shift problem and
propose a novel framework, transductive multi-view embedding, to solve it. The
second limitation is the prototype sparsity problem which refers to the fact
that for each target class, only a single prototype is available for zero-shot
learning given a semantic representation. To overcome this problem, a novel
heterogeneous multi-view hypergraph label propagation method is formulated for
zero-shot learning in the transductive embedding space. It effectively exploits
the complementary information offered by different semantic representations and
takes advantage of the manifold structures of multiple representation spaces in
a coherent manner. We demonstrate through extensive experiments that the
proposed approach (1) rectifies the projection shift between the auxiliary and
target domains, (2) exploits the complementarity of multiple semantic
representations, (3) significantly outperforms existing methods for both
zero-shot and N-shot recognition on three image and video benchmark datasets,
and (4) enables novel cross-view annotation tasks.
$\ell_1$-K-SVD: A Robust Dictionary Learning Algorithm With Simultaneous Update
Authors: Subhadip Mukherjee, Rupam Basu, Chandra Sekhar Seelamantula
Date: 2014-08-26 00:00:00
Tasks: Denoising, Dictionary Learning, SSIM

We develop a dictionary learning algorithm by minimizing the $\ell_1$
distortion metric on the data term, which is known to be robust for
non-Gaussian noise contamination. The proposed algorithm exploits the idea of
iterative minimization of weighted $\ell_2$ error. We refer to this algorithm
as $\ell_1$-K-SVD, where the dictionary atoms and the corresponding sparse
coefficients are simultaneously updated to minimize the $\ell_1$ objective,
resulting in noise-robustness. We demonstrate through experiments that the
$\ell_1$-K-SVD algorithm results in higher atom recovery rate compared with the
K-SVD and the robust dictionary learning (RDL) algorithm proposed by Lu et al.,
both in Gaussian and non-Gaussian noise conditions. We also show that, for
fixed values of sparsity, number of dictionary atoms, and data-dimension, the
$\ell_1$-K-SVD algorithm outperforms the K-SVD and RDL algorithms when the
training set available is small. We apply the proposed algorithm for denoising
natural images corrupted by additive Gaussian and Laplacian noise. The images
denoised using $\ell_1$-K-SVD are observed to have slightly higher peak
signal-to-noise ratio (PSNR) over K-SVD for Laplacian noise, but the
improvement in structural similarity index (SSIM) is significant (approximately
$0.1$) for lower values of input PSNR, indicating the efficacy of the $\ell_1$
metric.
An Introduction to Logics of Knowledge and Belief
Authors: Hans van Ditmarsch, Joseph Y. Halpern, Wiebe van der Hoek, Barteld Kooi
Date: 2015-03-03 00:00:00

This chapter provides an introduction to some basic concepts of epistemic
logic, basic formal languages, their semantics, and proof systems. It also
contains an overview of the handbook, and a brief history of epistemic logic
and pointers to the literature.
Context Forest for efficient object detection with large mixture models
Authors: Davide Modolo, Alexander Vezhnevets, Vittorio Ferrari
Date: 2015-03-03 00:00:00
Tasks: object-detection, Object Detection

We present Context Forest (ConF), a technique for predicting properties of
the objects in an image based on its global appearance. Compared to standard
nearest-neighbour techniques, ConF is more accurate, fast and memory efficient.
We train ConF to predict which aspects of an object class are likely to appear
in a given image (e.g. which viewpoint). This enables to speed-up
multi-component object detectors, by automatically selecting the most relevant
components to run on that image. This is particularly useful for detectors
trained from large datasets, which typically need many components to fully
absorb the data and reach their peak performance. ConF provides a speed-up of
2x for the DPM detector [1] and of 10x for the EE-SVM detector [2]. To show
ConF's generality, we also train it to predict at which locations objects are
likely to appear in an image. Incorporating this information in the detector
score improves mAP performance by about 2% by removing false positive
detections in unlikely locations.
Simple, Efficient, and Neural Algorithms for Sparse Coding
Authors: Sanjeev Arora, Rong Ge, Tengyu Ma, Ankur Moitra
Date: 2015-03-02 00:00:00

Sparse coding is a basic task in many fields including signal processing,
neuroscience and machine learning where the goal is to learn a basis that
enables a sparse representation of a given set of data, if one exists. Its
standard formulation is as a non-convex optimization problem which is solved in
practice by heuristics based on alternating minimization. Re- cent work has
resulted in several algorithms for sparse coding with provable guarantees, but
somewhat surprisingly these are outperformed by the simple alternating
minimization heuristics. Here we give a general framework for understanding
alternating minimization which we leverage to analyze existing heuristics and
to design new ones also with provable guarantees. Some of these algorithms seem
implementable on simple neural architectures, which was the original motivation
of Olshausen and Field (1997a) in introducing sparse coding. We also give the
first efficient algorithm for sparse coding that works almost up to the
information theoretic limit for sparse recovery on incoherent dictionaries. All
previous algorithms that approached or surpassed this limit run in time
exponential in some natural parameter. Finally, our algorithms improve upon the
sample complexity of existing approaches. We believe that our analysis
framework will have applications in other settings where simple iterative
algorithms are used.
Grouping and Recognition of Dot Patterns with Straight Offset Polygons
Authors: Toshiro Kubota
Date: 2015-03-02 00:00:00
Tasks: Object

When the boundary of a familiar object is shown by a series of isolated dots,
humans can often recognize the object with ease. This ability can be sustained
with addition of distracting dots around the object. However, such capability
has not been reproduced algorithmically on computers. We introduce a new
algorithm that groups a set of dots into multiple non-disjoint subsets. It
connects the dots into a spanning tree using the proximity cue. It then applies
the straight polygon transformation to an initial polygon derived from the
spanning tree. The straight polygon divides the space into polygons recursively
and each polygon can be viewed as grouping of a subset of the dots. The number
of polygons generated is O($n$). We also introduce simple shape selection and
recognition algorithms that can be applied to the grouping result. We used both
natural and synthetic images to show effectiveness of these algorithms.