OpenRaiser/Intern-Atlas huggingface dataset:
A Framework for the Analysis of Computational Imaging Systems with Practical Applications
Venue: arXiv cs.CV 2014
Year: 2014

Over the last decade, a number of Computational Imaging (CI) systems have been proposed for tasks such as motion deblurring, defocus deblurring and multispectral imaging. These techniques increase the amount of light reaching the sensor via multiplexing and then undo the deleterious effects of multiplexing by appropriate reconstruction algorithms. Given the widespread appeal and the considerable enthusiasm generated by these techniques, a detailed performance analysis of the benefits conferred by this approach is important. Unfortunately, a detailed analysis of CI has proven to be a challenging problem because performance depends equally on three components: (1) the optical multiplexing, (2) the noise characteristics of the sensor, and (3) the reconstruction algorithm. A few recent papers have performed analysis taking multiplexing and noise characteristics into account. However, analysis of CI systems under state-of-the-art reconstruction algorithms, most of which exploit signal prior models, has proven to be unwieldy. In this paper, we present a comprehensive analysis framework incorporating all three components. In order to perform this analysis, we model the signal priors using a Gaussian Mixture Model (GMM). A GMM prior confers two unique characteristics. Firstly, GMM satisfies the universal approximation property which says that any prior density function can be approximated to any fidelity using a GMM with appropriate number of mixtures. Secondly, a GMM prior lends itself to analytical tractability allowing us to derive simple expressions for the `minimum mean square error' (MMSE), which we use as a metric to characterize the performance of CI systems. We use our framework to analyze several previously proposed CI techniques, giving conclusive answer to the question: `How much performance gain is due to use of a signal prior and how much is due to multiplexing?
Parameterized Rural Postman Problem
Venue: arXiv cs.DS 2014
Year: 2014

The Directed Rural Postman Problem (DRPP) can be formulated as follows: given a strongly connected directed multigraph $D=(V,A)$ with nonnegative integral weights on the arcs, a subset $R$ of $A$ and a nonnegative integer $\ell$, decide whether $D$ has a closed directed walk containing every arc of $R$ and of total weight at most $\ell$. Let $k$ be the number of weakly connected components in the the subgraph of $D$ induced by $R$. Sorge et al. (2012) ask whether the DRPP is fixed-parameter tractable (FPT) when parameterized by $k$, i.e., whether there is an algorithm of running time $O^*(f(k))$ where $f$ is a function of $k$ only and the $O^*$ notation suppresses polynomial factors. Sorge et al. (2012) note that this question is of significant practical relevance and has been open for more than thirty years. Using an algebraic approach, we prove that DRPP has a randomized algorithm of running time $O^*(2^k)$ when $\ell$ is bounded by a polynomial in the number of vertices in $D$. We also show that the same result holds for the undirected version of DRPP, where $D$ is a connected undirected multigraph.
Knapsack Constrained Contextual Submodular List Prediction with Application to Multi-document Summarization
Venue: arXiv cs.LG 2014
Year: 2014

We study the problem of predicting a set or list of options under knapsack constraint. The quality of such lists are evaluated by a submodular reward function that measures both quality and diversity. Similar to DAgger (Ross et al., 2010), by a reduction to online learning, we show how to adapt two sequence prediction models to imitate greedy maximization under knapsack constraint problems: CONSEQOPT (Dey et al., 2012) and SCP (Ross et al., 2013). Experiments on extractive multi-document summarization show that our approach outperforms existing state-of-the-art methods.
Automatic Labeling for Entity Extraction in Cyber Security
Venue: arXiv cs.IR 2014
Year: 2014

Timely analysis of cyber-security information necessitates automated information extraction from unstructured text. While state-of-the-art extraction methods produce extremely accurate results, they require ample training data, which is generally unavailable for specialized applications, such as detecting security related entities; moreover, manual annotation of corpora is very costly and often not a viable solution. In response, we develop a very precise method to automatically label text from several data sources by leveraging related, domain-specific, structured data and provide public access to a corpus annotated with cyber-security entities. Next, we implement a Maximum Entropy Model trained with the average perceptron on a portion of our corpus ($\sim$750,000 words) and achieve near perfect precision, recall, and accuracy, with training times under 17 seconds.
A Principled Approach to Bridging the Gap between Graph Data and their Schemas
Venue: arXiv cs.DB 2014
Year: 2014

Although RDF graphs have schema information associated with them, in practice it is very common to find cases in which data do not fully conform to their schema. A prominent example of this is DBpedia, which is RDF data extracted from Wikipedia, a publicly editable source of information. In such situations, it becomes interesting to study the structural properties of the actual data, because the schema gives an incomplete description of the organization of a dataset. In this paper we have approached the study of the structuredness of an RDF graph in a principled way: we propose a framework for specifying structuredness functions, which gauge the degree to which an RDF graph conforms to a schema. In particular, we first define a formal language for specifying structuredness functions with expressions we call rules. This language allows a user or a database administrator to state a rule to which an RDF graph may fully or partially conform. Then we consider the issue of discovering a refinement of a sort (type) by partitioning the dataset into subsets whose structuredness is over a specified threshold. In particular, we prove that the natural decision problem associated to this refinement problem is NP-complete, and we provide a natural translation of this problem into Integer Linear Programming (ILP). Finally, we test this ILP solution with two real world datasets, DBpedia Persons and WordNet Nouns, and 4 different and intuitive rules, which gauge the structuredness in different ways. The rules give meaningful refinements of the datasets, showing that our language can be a powerful tool for understanding the structure of RDF data.
New Algorithms for Learning Incoherent and Overcomplete Dictionaries
Venue: arXiv cs.DS 2014
Year: 2014

In sparse recovery we are given a matrix $A$ (the dictionary) and a vector of the form $A X$ where $X$ is sparse, and the goal is to recover $X$. This is a central notion in signal processing, statistics and machine learning. But in applications such as sparse coding, edge detection, compression and super resolution, the dictionary $A$ is unknown and has to be learned from random examples of the form $Y = AX$ where $X$ is drawn from an appropriate distribution --- this is the dictionary learning problem. In most settings, $A$ is overcomplete: it has more columns than rows. This paper presents a polynomial-time algorithm for learning overcomplete dictionaries; the only previously known algorithm with provable guarantees is the recent work of Spielman, Wang and Wright who gave an algorithm for the full-rank case, which is rarely the case in applications. Our algorithm applies to incoherent dictionaries which have been a central object of study since they were introduced in seminal work of Donoho and Huo. In particular, a dictionary is $μ$-incoherent if each pair of columns has inner product at most $μ/ \sqrt{n}$. The algorithm makes natural stochastic assumptions about the unknown sparse vector $X$, which can contain $k \leq c \min(\sqrt{n}/μ\log n, m^{1/2 -η})$ non-zero entries (for any $η> 0$). This is close to the best $k$ allowable by the best sparse recovery algorithms even if one knows the dictionary $A$ exactly. Moreover, both the running time and sample complexity depend on $\log 1/ε$, where $ε$ is the target accuracy, and so our algorithms converge very quickly to the true dictionary. Our algorithm can also tolerate substantial amounts of noise provided it is incoherent with respect to the dictionary (e.g., Gaussian). In the noisy setting, our running time and sample complexity depend polynomially on $1/ε$, and this is necessary.
Joint Video and Text Parsing for Understanding Events and Answering Queries
Venue: arXiv cs.CV 2014
Year: 2014

We propose a framework for parsing video and text jointly for understanding events and answering user queries. Our framework produces a parse graph that represents the compositional structures of spatial information (objects and scenes), temporal information (actions and events) and causal information (causalities between events and fluents) in the video and text. The knowledge representation of our framework is based on a spatial-temporal-causal And-Or graph (S/T/C-AOG), which jointly models possible hierarchical compositions of objects, scenes and events as well as their interactions and mutual contexts, and specifies the prior probabilistic distribution of the parse graphs. We present a probabilistic generative model for joint parsing that captures the relations between the input video/text, their corresponding parse graphs and the joint parse graph. Based on the probabilistic model, we propose a joint parsing system consisting of three modules: video parsing, text parsing and joint inference. Video parsing and text parsing produce two parse graphs from the input video and text respectively. The joint inference module produces a joint parse graph by performing matching, deduction and revision on the video and text parse graphs. The proposed framework has the following objectives: Firstly, we aim at deep semantic parsing of video and text that goes beyond the traditional bag-of-words approaches; Secondly, we perform parsing and reasoning across the spatial, temporal and causal dimensions based on the joint S/T/C-AOG representation; Thirdly, we show that deep joint parsing facilitates subsequent applications such as generating narrative text descriptions and answering queries in the forms of who, what, when, where and why. We empirically evaluated our system based on comparison against ground-truth as well as accuracy of query answering and obtained satisfactory results.
Near-optimal Frequency-weighted Interpolatory Model Reduction
Venue: arXiv cs.SY 2014
Year: 2014

This paper develops an interpolatory framework for weighted-$\mathcal{H}_2$ model reduction of MIMO dynamical systems. A new representation of the weighted-$\mathcal{H}_2$ inner products in MIMO settings is introduced and used to derive associated first-order necessary conditions satisfied by optimal weighted-$\mathcal{H}_2$ reduced-order models. Equivalence of these new interpolatory conditions with earlier Riccati-based conditions given by Halevi is also shown. An examination of realizations for equivalent weighted-$\mathcal{H}_2$ systems leads then to an algorithm that remains tractable for large state-space dimension. Several numerical examples illustrate the effectiveness of this approach and its competitiveness with Frequency Weighted Balanced Truncation and an earlier interpolatory approach, the Weighted Iterative Rational Krylov Algorithm.
Tagging Scientific Publications using Wikipedia and Natural Language Processing Tools. Comparison on the ArXiv Dataset
Venue: arXiv cs.CL 2014
Year: 2014

In this work, we compare two simple methods of tagging scientific publications with labels reflecting their content. As a first source of labels Wikipedia is employed, second label set is constructed from the noun phrases occurring in the analyzed corpus. We examine the statistical properties and the effectiveness of both approaches on the dataset consisting of abstracts from 0.7 million of scientific documents deposited in the ArXiv preprint collection. We believe that obtained tags can be later on applied as useful document features in various machine learning tasks (document similarity, clustering, topic modelling, etc.).
Joint Sparse Recovery Method for Compressed Sensing with Structured Dictionary Mismatches
Venue: arXiv cs.IT 2014
Year: 2014

In traditional compressed sensing theory, the dictionary matrix is given a priori, whereas in real applications this matrix suffers from random noise and fluctuations. In this paper we consider a signal model where each column in the dictionary matrix is affected by a structured noise. This formulation is common in direction-of-arrival (DOA) estimation of off-grid targets, encountered in both radar systems and array processing. We propose to use joint sparse signal recovery to solve the compressed sensing problem with structured dictionary mismatches and also give an analytical performance bound on this joint sparse recovery. We show that, under mild conditions, the reconstruction error of the original sparse signal is bounded by both the sparsity and the noise level in the measurement model. Moreover, we implement fast first-order algorithms to speed up the computing process. Numerical examples demonstrate the good performance of the proposed algorithm, and also show that the joint-sparse recovery method yields a better reconstruction result than existing methods. By implementing the joint sparse recovery method, the accuracy and efficiency of DOA estimation are improved in both passive and active sensing cases.
Efficient Enumeration of Chordless Cycles
Venue: arXiv cs.DS 2014
Year: 2014

In a finite undirected simple graph, a {\it chordless cycle} is an induced subgraph which is a cycle. We propose two algorithms to enumerate all chordless cycles of such a graph. Compared to other similar algorithms, the proposed algorithms have the advantage of finding each chordless cycle only once. To ensure this, we introduced the concepts of vertex labeling and initial valid vertex triplet. To guarantee that the expansion of a given chordless path will always lead to a chordless cycle, we use a breadth-first search in a subgraph obtained by the elimination of many of the vertices from the original graph. The resulting algorithm has time complexity $\mathcal{O}(n + m)$ in the output size, where $n$ is the number of vertices and $m$ is the number of edges.
Logspace computations in graph products
Venue: arXiv cs.DM 2014
Year: 2014

We consider three important and well-studied algorithmic problems in group theory: the word, geodesic, and conjugacy problem. We show transfer results from individual groups to graph products. We concentrate on logspace complexity because the challenge is actually in small complexity classes, only. The most difficult transfer result is for the conjugacy problem. We have a general result for graph products, but even in the special case of a graph group the result is new. Graph groups are closely linked to the theory of Mazurkiewicz traces which form an algebraic model for concurrent processes. Our proofs are combinatorial and based on well-known concepts in trace theory. We also use rewriting techniques over traces. For the group-theoretical part we apply Bass-Serre theory. But as we need explicit formulae and as we design concrete algorithms all our group-theoretical calculations are completely explicit and accessible to non-specialists.
Practical Matrix Completion and Corruption Recovery using Proximal Alternating Robust Subspace Minimization
Venue: arXiv cs.CV 2014
Year: 2014

Low-rank matrix completion is a problem of immense practical importance. Recent works on the subject often use nuclear norm as a convex surrogate of the rank function. Despite its solid theoretical foundation, the convex version of the problem often fails to work satisfactorily in real-life applications. Real data often suffer from very few observations, with support not meeting the random requirements, ubiquitous presence of noise and potentially gross corruptions, sometimes with these simultaneously occurring. This paper proposes a Proximal Alternating Robust Subspace Minimization (PARSuMi) method to tackle the three problems. The proximal alternating scheme explicitly exploits the rank constraint on the completed matrix and uses the $\ell_0$ pseudo-norm directly in the corruption recovery step. We show that the proposed method for the non-convex and non-smooth model converges to a stationary point. Although it is not guaranteed to find the global optimal solution, in practice we find that our algorithm can typically arrive at a good local minimizer when it is supplied with a reasonably good starting point based on convex optimization. Extensive experiments with challenging synthetic and real data demonstrate that our algorithm succeeds in a much larger range of practical problems where convex optimization fails, and it also outperforms various state-of-the-art algorithms.
Topology preserving thinning for cell complexes
Venue: arXiv cs.CV 2014
Year: 2014

A topology preserving skeleton is a synthetic representation of an object that retains its topology and many of its significant morphological properties. The process of obtaining the skeleton, referred to as skeletonization or thinning, is a very active research area. It plays a central role in reducing the amount of information to be processed during image analysis and visualization, computer-aided diagnosis or by pattern recognition algorithms. This paper introduces a novel topology preserving thinning algorithm which removes \textit{simple cells}---a generalization of simple points---of a given cell complex. The test for simple cells is based on \textit{acyclicity tables} automatically produced in advance with homology computations. Using acyclicity tables render the implementation of thinning algorithms straightforward. Moreover, the fact that tables are automatically filled for all possible configurations allows to rigorously prove the generality of the algorithm and to obtain fool-proof implementations. The novel approach enables, for the first time, according to our knowledge, to thin a general unstructured simplicial complex. Acyclicity tables for cubical and simplicial complexes and an open source implementation of the thinning algorithm are provided as additional material to allow their immediate use in the vast number of practical applications arising in medical imaging and beyond.
Learning Transformations for Clustering and Classification
Venue: arXiv cs.CV 2014
Year: 2014

A low-rank transformation learning framework for subspace clustering and classification is here proposed. Many high-dimensional data, such as face images and motion sequences, approximately lie in a union of low-dimensional subspaces. The corresponding subspace clustering problem has been extensively studied in the literature to partition such high-dimensional data into clusters corresponding to their underlying low-dimensional subspaces. However, low-dimensional intrinsic structures are often violated for real-world observations, as they can be corrupted by errors or deviate from ideal models. We propose to address this by learning a linear transformation on subspaces using matrix rank, via its convex surrogate nuclear norm, as the optimization criteria. The learned linear transformation restores a low-rank structure for data from the same subspace, and, at the same time, forces a a maximally separated structure for data from different subspaces. In this way, we reduce variations within subspaces, and increase separation between subspaces for a more robust subspace clustering. This proposed learned robust subspace clustering framework significantly enhances the performance of existing subspace clustering methods. Basic theoretical results here presented help to further support the underlying framework. To exploit the low-rank structures of the transformed subspaces, we further introduce a fast subspace clustering technique, which efficiently combines robust PCA with sparse modeling. When class labels are present at the training stage, we show this low-rank transformation framework also significantly enhances classification performance. Extensive experiments using public datasets are presented, showing that the proposed approach significantly outperforms state-of-the-art methods for subspace clustering and classification.
Secure Layered Transmission in Multicast Systems with Wireless Information and Power Transfer
Venue: arXiv cs.IT 2014
Year: 2014

This paper considers downlink multicast transmit beamforming for secure layered transmission systems with wireless simultaneous information and power transfer. We study the power allocation algorithm design for minimizing the total transmit power in the presence of passive eavesdroppers and energy harvesting receivers. The algorithm design is formulated as a non-convex optimization problem. Our problem formulation promotes the dual use of energy signals in providing secure communication and facilitating efficient energy transfer. Besides, we take into account a minimum required power for energy harvesting at the idle receivers and heterogeneous quality of service (QoS) requirements for the multicast video receivers. In light of the intractability of the problem, we reformulate the considered problem by replacing a non-convex probabilistic constraint with a convex deterministic constraint. Then, a semidefinite programming relaxation (SDR) approach is adopted to obtain an upper solution for the reformulated problem. Subsequently, sufficient conditions for the global optimal solution of the reformulated problem are revealed. Furthermore, we propose two suboptimal power allocation schemes based on the upper bound solution. Simulation results demonstrate the excellent performance and significant transmit power savings achieved by the proposed schemes compared to isotropic energy signal generation.
Combination of Multiple Bipartite Ranking for Web Content Quality Evaluation
Venue: arXiv cs.IR 2014
Year: 2014

Web content quality estimation is crucial to various web content processing applications. Our previous work applied Bagging + C4.5 to achive the best results on the ECML/PKDD Discovery Challenge 2010, which is the comibination of many point-wise rankinig models. In this paper, we combine multiple pair-wise bipartite ranking learner to solve the multi-partite ranking problems for the web quality estimation. In encoding stage, we present the ternary encoding and the binary coding extending each rank value to $L - 1$ (L is the number of the different ranking value). For the decoding, we discuss the combination of multiple ranking results from multiple bipartite ranking models with the predefined weighting and the adaptive weighting. The experiments on ECML/PKDD 2010 Discovery Challenge datasets show that \textit{binary coding} + \textit{predefined weighting} yields the highest performance in all four combinations and furthermore it is better than the best results reported in ECML/PKDD 2010 Discovery Challenge competition.