OpenRaiser/Intern-Atlas huggingface dataset:
Lifting for Blind Deconvolution in Random Mask Imaging: Identifiability and Convex Relaxation
Venue: arXiv cs.IT 2015
Year: 2015

In this paper we analyze the blind deconvolution of an image and an unknown blur in a coded imaging system. The measurements consist of subsampled convolution of an unknown blurring kernel with multiple random binary modulations (coded masks) of the image. To perform the deconvolution, we consider a standard lifting of the image and the blurring kernel that transforms the measurements into a set of linear equations of the matrix formed by their outer product. Any rank-one solution to this system of equation provides a valid pair of an image and a blur. We first express the necessary and sufficient conditions for the uniqueness of a rank-one solution under some additional assumptions (uniform subsampling and no limit on the number of coded masks). These conditions are special case of a previously established result regarding identifiability in the matrix completion problem. We also characterize a low-dimensional subspace model for the blur kernel that is sufficient to guarantee identifiability, including the interesting instance of "bandpass"` blur kernels. Next, assuming the bandpass model for the blur kernel, we show that the image and the blur kernel can be found using nuclear norm minimization. Our main results show that recovery is achieved (with high probability) when the number of masks is on the order of $μ\log^{2}L\,\log\frac{Le}μ\,\log\log\left(N+1\right)$ where $μ$ is the \emph{coherence} of the blur, $L$ is the dimension of the image, and $N$ is the number of measured samples per mask.
On the complexity of finite valued functions
Venue: arXiv cs.CC 2015
Year: 2015

The essential variables in a finite function $f$ are defined as variables which occur in $f$ and weigh with the values of that function. The number of essential variables is an important measure of complexity for discrete functions. When replacing some variables in a function with constants the resulting functions are called subfunctions, and when replacing all essential variables in a function with constants we obtain an implementation of this function. Such an implementation corresponds with a path in an ordered decision diagram (ODD) of the function which connects the root with a leaf of the diagram. The sets of essential variables in subfunctions of $f$ are called separable in $f$. In this paper we study several properties of separable sets of variables in functions which directly impact on the number of implementations and subfunctions in these functions. We define equivalence relations which classify the functions of $k$-valued logic into classes with same number of implementations, subfunctions or separable sets. These relations induce three transformation groups which are compared with the lattice of all subgroups of restricted affine group (RAG). This allows us to solve several important computational and combinatorial problems.
QANUS: An Open-source Question-Answering Platform
Venue: arXiv cs.IR 2015
Year: 2015

In this paper, we motivate the need for a publicly available, generic software framework for question-answering (QA) systems. We present an open-source QA framework QANUS which researchers can leverage on to build new QA systems easily and rapidly. The framework implements much of the code that will otherwise have been repeated across different QA systems. To demonstrate the utility and practicality of the framework, we further present a fully functioning factoid QA system QA-SYS built on top of QANUS.
Efficient reduction of Kappa models by static inspection of the rule-set
Venue: arXiv cs.CE 2015
Year: 2015

When designing genetic circuits, the typical primitives used in major existing modelling formalisms are gene interaction graphs, where edges between genes denote either an activation or inhibition relation. However, when designing experiments, it is important to be precise about the low-level mechanistic details as to how each such relation is implemented. The rule-based modelling language Kappa allows to unambiguously specify mechanistic details such as DNA binding sites, dimerisation of transcription factors, or co-operative interactions. However, such a detailed description comes with complexity and computationally costly execution. We propose a general method for automatically transforming a rule-based program, by eliminating intermediate species and adjusting the rate constants accordingly. Our method consists of searching for those interaction patterns known to be amenable to equilibrium approximations (e.g. Michaelis-Menten scheme). The reduced model is efficiently obtained by static inspection over the rule-set, and it represents a particular theoretical limit of the original model. The Bhattacharyya distance is proposed as a metric to estimate the reduction error for a given observable. The tool is tested on a detailed rule-based model of a $λ$-phage switch, which lists $96$ rules and $16$ agents. The reduced model has $11$ rules and $5$ agents, and provides a dramatic reduction in simulation time of several orders of magnitude.
How Perfect Offline Wallets Can Still Leak Bitcoin Private Keys
Venue: arXiv cs.CR 2015
Year: 2015

ECDSA has become a popular choice as lightweight alternative to RSA and classic DL based signature algorithms in recent years. As standardized, the signature produced by ECDSA for a pair of a message and a key is not deterministic. This work shows how this non-deterministic choice can be exploited by an attacker to leak private information through the signature without any side channels, an attack first discovered by Young and Yung for classic DL-based cryptosystems in 1997, and how this attack affects the application of ECDSA in the Bitcoin protocol.
An Empirical Study of the L2-Boost technique with Echo State Networks
Venue: arXiv cs.LG 2015
Year: 2015

A particular case of Recurrent Neural Network (RNN) was introduced at the beginning of the 2000s under the name of Echo State Networks (ESNs). The ESN model overcomes the limitations during the training of the RNNs while introducing no significant disadvantages. Although the model presents some well-identified drawbacks when the parameters are not well initialised. The performance of an ESN is highly dependent on its internal parameters and pattern of connectivity of the hidden-hidden weights Often, the tuning of the network parameters can be hard and can impact in the accuracy of the models. In this work, we investigate the performance of a specific boosting technique (called L2-Boost) with ESNs as single predictors. The L2-Boost technique has been shown to be an effective tool to combine "weak" predictors in regression problems. In this study, we use an ensemble of random initialized ESNs (without control their parameters) as "weak" predictors of the boosting procedure. We evaluate our approach on five well-know time-series benchmark problems. Additionally, we compare this technique with a baseline approach that consists of averaging the prediction of an ensemble of ESNs.
A Model Study of an All-Digital, Discrete-Time and Embedded Linear Regulator
Venue: arXiv cs.AR 2015
Year: 2015

With an increasing number of power-states, finer- grained power management and larger dynamic ranges of digital circuits, the integration of compact, scalable linear-regulators embedded deep within logic blocks has become important. While analog linear-regulators have traditionally been used in digital ICs, the need for digitally implementable designs that can be synthesized and embedded in digital functional units for ultra fine- grained power management has emerged. This paper presents the circuit design and control models of an all-digital, discrete-time linear regulator and explores the parametric design space for transient response time and loop stability.
Stochastic block model and exploratory analysis in signed networks
Venue: arXiv cs.SI 2015
Year: 2015

We propose a generalized stochastic block model to explore the mesoscopic structures in signed networks by grouping vertices that exhibit similar positive and negative connection profiles into the same cluster. In this model, the group memberships are viewed as hidden or unobserved quantities, and the connection patterns between groups are explicitly characterized by two block matrices, one for positive links and the other for negative links. By fitting the model to the observed network, we can not only extract various structural patterns existing in the network without prior knowledge, but also recognize what specific structures we obtained. Furthermore, the model parameters provide vital clues about the probabilities that each vertex belongs to different groups and the centrality of each vertex in its corresponding group. This information sheds light on the discovery of the networks' overlapping structures and the identification of two types of important vertices, which serve as the cores of each group and the bridges between different groups, respectively. Experiments on a series of synthetic and real-life networks show the effectiveness as well as the superiority of our model.
Ultimate Intelligence Part I: Physical Completeness and Objectivity of Induction
Venue: arXiv cs.AI 2015
Year: 2015

We propose that Solomonoff induction is complete in the physical sense via several strong physical arguments. We also argue that Solomonoff induction is fully applicable to quantum mechanics. We show how to choose an objective reference machine for universal induction by defining a physical message complexity and physical message probability, and argue that this choice dissolves some well-known objections to universal induction. We also introduce many more variants of physical message complexity based on energy and action, and discuss the ramifications of our proposals.
Evaluation of Predictive Data Mining Algorithms in Erythemato-Squamous Disease Diagnosis
Venue: arXiv cs.LG 2015
Year: 2015

A lot of time is spent searching for the most performing data mining algorithms applied in clinical diagnosis. The study set out to identify the most performing predictive data mining algorithms applied in the diagnosis of Erythemato-squamous diseases. The study used Naive Bayes, Multilayer Perceptron and J48 decision tree induction to build predictive data mining models on 366 instances of Erythemato-squamous diseases datasets. Also, 10-fold cross-validation and sets of performance metrics were used to evaluate the baseline predictive performance of the classifiers. The comparative analysis shows that the Naive Bayes performed best with accuracy of 97.4%, Multilayer Perceptron came out second with accuracy of 96.6%, and J48 came out the worst with accuracy of 93.5%. The evaluation of these classifiers on clinical datasets, gave an insight into the predictive ability of different data mining algorithms applicable in clinical diagnosis especially in the diagnosis of Erythemato-squamous diseases.
Cross-language Wikipedia Editing of Okinawa, Japan
Venue: arXiv cs.CY 2015
Year: 2015

This article analyzes users who edit Wikipedia articles about Okinawa, Japan, in English and Japanese. It finds these users are among the most active and dedicated users in their primary languages, where they make many large, high-quality edits. However, when these users edit in their non-primary languages, they tend to make edits of a different type that are overall smaller in size and more often restricted to the narrow set of articles that exist in both languages. Design changes to motivate wider contributions from users in their non-primary languages and to encourage multilingual users to transfer more information across language divides are presented.
On the Complexity of Noncommutative Polynomial Factorization
Venue: arXiv cs.CC 2015
Year: 2015

In this paper we study the complexity of factorization of polynomials in the free noncommutative ring $\mathbb{F}\langle x_1,x_2,\dots,x_n\rangle$ of polynomials over the field $\mathbb{F}$ and noncommuting variables $x_1,x_2,\ldots,x_n$. Our main results are the following. Although $\mathbb{F}\langle x_1,x_2,\dots,x_n \rangle$ is not a unique factorization ring, we note that variable-disjoint factorization in $\mathbb{F}\langle x_1,x_2,\dots,x_n \rangle$ has the uniqueness property. Furthermore, we prove that computing the variable-disjoint factorization is polynomial-time equivalent to Polynomial Identity Testing (both when the input polynomial is given by an arithmetic circuit or an algebraic branching program). We also show that variable-disjoint factorization in the black-box setting can be efficiently computed (where the factors computed will be also given by black-boxes, analogous to the work [KT91] in the commutative setting). As a consequence of the previous result we show that homogeneous noncommutative polynomials and multilinear noncommutative polynomials have unique factorizations in the usual sense, which can be efficiently computed. Finally, we discuss a polynomial decomposition problem in $\mathbb{F}\langle x_1,x_2,\dots,x_n\rangle$ which is a natural generalization of homogeneous polynomial factorization and prove some complexity bounds for it.
Group-based ranking method for online rating systems with spamming attacks
Venue: arXiv cs.IR 2015
Year: 2015

Ranking problem has attracted much attention in real systems. How to design a robust ranking method is especially significant for online rating systems under the threat of spamming attacks. By building reputation systems for users, many well-performed ranking methods have been applied to address this issue. In this Letter, we propose a group-based ranking method that evaluates users' reputations based on their grouping behaviors. More specifically, users are assigned with high reputation scores if they always fall into large rating groups. Results on three real data sets indicate that the present method is more accurate and robust than correlation-based method in the presence of spamming attacks.
Clustering Boolean Tensors
Venue: arXiv cs.NA 2015
Year: 2015

Tensor factorizations are computationally hard problems, and in particular, are often significantly harder than their matrix counterparts. In case of Boolean tensor factorizations -- where the input tensor and all the factors are required to be binary and we use Boolean algebra -- much of that hardness comes from the possibility of overlapping components. Yet, in many applications we are perfectly happy to partition at least one of the modes. In this paper we investigate what consequences does this partitioning have on the computational complexity of the Boolean tensor factorizations and present a new algorithm for the resulting clustering problem. This algorithm can alternatively be seen as a particularly regularized clustering algorithm that can handle extremely high-dimensional observations. We analyse our algorithms with the goal of maximizing the similarity and argue that this is more meaningful than minimizing the dissimilarity. As a by-product we obtain a PTAS and an efficient 0.828-approximation algorithm for rank-1 binary factorizations. Our algorithm for Boolean tensor clustering achieves high scalability, high similarity, and good generalization to unseen data with both synthetic and real-world data sets.
Differential Search Algorithm-based Parametric Optimization of Fuzzy Generalized Eigenvalue Proximal Support Vector Machine
Venue: arXiv cs.LG 2015
Year: 2015

Support Vector Machine (SVM) is an effective model for many classification problems. However, SVM needs the solution of a quadratic program which require specialized code. In addition, SVM has many parameters, which affects the performance of SVM classifier. Recently, the Generalized Eigenvalue Proximal SVM (GEPSVM) has been presented to solve the SVM complexity. In real world applications data may affected by error or noise, working with this data is a challenging problem. In this paper, an approach has been proposed to overcome this problem. This method is called DSA-GEPSVM. The main improvements are carried out based on the following: 1) a novel fuzzy values in the linear case. 2) A new Kernel function in the nonlinear case. 3) Differential Search Algorithm (DSA) is reformulated to find near optimal values of the GEPSVM parameters and its kernel parameters. The experimental results show that the proposed approach is able to find the suitable parameter values, and has higher classification accuracy compared with some other algorithms.
On the trade-off between control performance and communication cost in event-triggered control
Venue: arXiv cs.SY 2015
Year: 2015

We consider a stochastic system where the communication between the controller and the actuator is triggered by a threshold-based rule. The communication is performed across an unreliable link that stochastically erases transmitted packets. To decrease the communication burden, and as a partial protection against dropped packets, the controller sends a sequence of control commands to the actuator in each packet. These commands are stored in a buffer and applied sequentially until the next control packet arrives. In this context, we study dead-beat control laws and compute the expected linear-quadratic loss of the closed-loop system for any given event-threshold. Furthermore, we provide analytical expressions that quantify the trade-off between the communication cost and the control performance of event-triggered control systems. Numerical examples demonstrate the effectiveness of the proposed framework.
Adaptive Objectness for Object Tracking
Venue: arXiv cs.CV 2015
Year: 2015

Object tracking is a long standing problem in vision. While great efforts have been spent to improve tracking performance, a simple yet reliable prior knowledge is left unexploited: the target object in tracking must be an object other than non-object. The recently proposed and popularized objectness measure provides a natural way to model such prior in visual tracking. Thus motivated, in this paper we propose to adapt objectness for visual object tracking. Instead of directly applying an existing objectness measure that is generic and handles various objects and environments, we adapt it to be compatible to the specific tracking sequence and object. More specifically, we use the newly proposed BING objectness as the base, and then train an object-adaptive objectness for each tracking task. The training is implemented by using an adaptive support vector machine that integrates information from the specific tracking target into the BING measure. We emphasize that the benefit of the proposed adaptive objectness, named ADOBING, is generic. To show this, we combine ADOBING with seven top performed trackers in recent evaluations. We run the ADOBING-enhanced trackers with their base trackers on two popular benchmarks, the CVPR2013 benchmark (50 sequences) and the Princeton Tracking Benchmark (100 sequences). On both benchmarks, our methods not only consistently improve the base trackers, but also achieve the best known performances. Noting that the way we integrate objectness in visual tracking is generic and straightforward, we expect even more improvement by using tracker-specific objectness.
Influence of Behavioral Models on Multiuser Channel Capacity
Venue: arXiv cs.IT 2015
Year: 2015

In order to characterize the channel capacity of a wavelength channel in a wavelength-division multiplexed (WDM) system, statistical models are needed for the transmitted signals on the other wavelengths. For example, one could assume that the transmitters for all wavelengths are configured independently of each other, that they use the same signal power, or that they use the same modulation format. In this paper, it is shown that these so-called behavioral models have a profound impact on the single-wavelength achievable information rate. This is demonstrated by establishing, for the first time, upper and lower bounds on the maximum achievable rate under various behavioral models, for a rudimentary WDM channel model.
A Study on Clustering for Clustering Based Image De-Noising
Venue: arXiv cs.CV 2015
Year: 2015

In this paper, the problem of de-noising of an image contaminated with Additive White Gaussian Noise (AWGN) is studied. This subject is an open problem in signal processing for more than 50 years. Local methods suggested in recent years, have obtained better results than global methods. However by more intelligent training in such a way that first, important data is more effective for training, second, clustering in such way that training blocks lie in low-rank subspaces, we can design a dictionary applicable for image de-noising and obtain results near the state of the art local methods. In the present paper, we suggest a method based on global clustering of image constructing blocks. As the type of clustering plays an important role in clustering-based de-noising methods, we address two questions about the clustering. The first, which parts of the data should be considered for clustering? and the second, what data clustering method is suitable for de-noising.? Then clustering is exploited to learn an over complete dictionary. By obtaining sparse decomposition of the noisy image blocks in terms of the dictionary atoms, the de-noised version is achieved. In addition to our framework, 7 popular dictionary learning methods are simulated and compared. The results are compared based on two major factors: (1) de-noising performance and (2) execution time. Experimental results show that our dictionary learning framework outperforms its competitors in terms of both factors.
Two Answers to a Common Question on Diagonalization
Venue: arXiv cs.DM 2015
Year: 2015

A common question from students on the usual diagonalization proof for the uncountability of the set of real numbers is: when a representation of real numbers, such as the decimal expansions of real numbers, allows us to use the diagonalization argument to prove that the set of real numbers is uncountable, why can't we similarly apply the diagonalization argument to rational numbers in the same representation? why doesn't the argument similarly prove that the set of rational numbers is uncountable too? We consider two answers to this question. We first discuss an answer that is based on the familiar decimal expansions. We then present an unconventional answer that is based on continued fractions.
Efficient Online Relative Comparison Kernel Learning
Venue: arXiv cs.LG 2015
Year: 2015

Learning a kernel matrix from relative comparison human feedback is an important problem with applications in collaborative filtering, object retrieval, and search. For learning a kernel over a large number of objects, existing methods face significant scalability issues inhibiting the application of these methods to settings where a kernel is learned in an online and timely fashion. In this paper we propose a novel framework called Efficient online Relative comparison Kernel LEarning (ERKLE), for efficiently learning the similarity of a large set of objects in an online manner. We learn a kernel from relative comparisons via stochastic gradient descent, one query response at a time, by taking advantage of the sparse and low-rank properties of the gradient to efficiently restrict the kernel to lie in the space of positive semidefinite matrices. In addition, we derive a passive-aggressive online update for minimally satisfying new relative comparisons as to not disrupt the influence of previously obtained comparisons. Experimentally, we demonstrate a considerable improvement in speed while obtaining improved or comparable accuracy compared to current methods in the online learning setting.