OpenRaiser/Intern-Atlas huggingface dataset:
Matrix recovery using Split Bregman
Venue: arXiv cs.NA 2013
Year: 2013

In this paper we address the problem of recovering a matrix, with inherent low rank structure, from its lower dimensional projections. This problem is frequently encountered in wide range of areas including pattern recognition, wireless sensor networks, control systems, recommender systems, image/video reconstruction etc. Both in theory and practice, the most optimal way to solve the low rank matrix recovery problem is via nuclear norm minimization. In this paper, we propose a Split Bregman algorithm for nuclear norm minimization. The use of Bregman technique improves the convergence speed of our algorithm and gives a higher success rate. Also, the accuracy of reconstruction is much better even for cases where small number of linear measurements are available. Our claim is supported by empirical results obtained using our algorithm and its comparison to other existing methods for matrix recovery. The algorithms are compared on the basis of NMSE, execution time and success rate for varying ranks and sampling ratios.
Game Theoretic Approach to the Stabilization of Heterogeneous Multiagent Systems Using Subsidy
Venue: arXiv cs.GT 2013
Year: 2013

We consider a multiagent system consisting of selfish and heterogeneous agents. Its behavior is modeled by multipopulation replicator dynamics, where payoff functions of populations are different from each other. In general, there exist several equilibrium points in the replicator dynamics. In order to stabilize a desirable equilibrium point, we introduce a controller called a government which controls the behaviors of agents by offering them subsidies. In previous work, it is assumed that the government determines the subsidies based on the populations the agents belong to. In general, however, the government cannot identify the members of each population. In this paper, we assume that the government observes the action of each agent and determines the subsidies based on the observed action profile. Then, we model the controlled behaviors of the agents using replicator dynamics with feedback. We derive a stabilization condition of the target equilibrium point in the replicator dynamics.
Multiple routes transmitted epidemics on multiplex networks
Venue: arXiv cs.SI 2013
Year: 2013

This letter investigates the multiple routes transmitted epidemic process on multiplex networks. We propose detailed theoretical analysis that allows us to accurately calculate the epidemic threshold and outbreak size. It is found that the epidemic can spread across the multiplex network even if all the network layers are well below their respective epidemic thresholds. Strong positive degree-degree correlation of nodes in multiplex network could lead to a much lower epidemic threshold and a relatively smaller outbreak size. However, the average similarity of neighbors from different layers of nodes has no obvious effect on the epidemic threshold and outbreak size.
The performance evaluation of IEEE 802.16 physical layer in the basis of bit error rate considering reference channel models
Venue: arXiv cs.NI 2013
Year: 2013

Fixed Broadband Wireless Access is a promising technology which can offer high speed data rate from transmitting end to customer end which can offer high speed text, voice, and video data. IEEE 802.16 WirelessMAN is a standard that specifies medium access control layer and a set of PHY layer to fixed and mobile BWA in broad range of frequencies and it supports equipment manufacturers due to its robust performance in multipath environment. Consequently WiMAX forum has adopted this version to develop the network world wide. In this paper the performance of IEEE 802.16 OFDM PHY Layer has been investigated by using the simulation model in Matlab. The Stanford University Interim (SUI) channel models are selected for the performance evaluation of this standard. The Ideal Channel estimation is considered in this work and the performance evaluation is observed in the basis of BER.
A Primal Dual Active Set Algorithm with Continuation for Compressed Sensing
Venue: arXiv cs.IT 2013
Year: 2013

The success of compressed sensing relies essentially on the ability to efficiently find an approximately sparse solution to an under-determined linear system. In this paper, we developed an efficient algorithm for the sparsity promoting $\ell_1$-regularized least squares problem by coupling the primal dual active set strategy with a continuation technique (on the regularization parameter). In the active set strategy, we first determine the active set from primal and dual variables, and then update the primal and dual variables by solving a low-dimensional least square problem on the active set, which makes the algorithm very efficient. The continuation technique globalizes the convergence of the algorithm, with provable global convergence under restricted isometry property (RIP). Further, we adopt two alternative methods, i.e., a modified discrepancy principle and a Bayesian information criterion, to choose the regularization parameter. Numerical experiments indicate that our algorithm is very competitive with state-of-the-art algorithms in terms of accuracy and efficiency.
Complexity Results for Rainbow Matchings
Venue: arXiv cs.DM 2013
Year: 2013

A rainbow matching in an edge-colored graph is a matching whose edges have distinct colors. We address the complexity issue of the following problem, \mrbm: Given an edge-colored graph $G$, how large is the largest rainbow matching in $G$? We present several sharp contrasts in the complexity of this problem. We show, among others, that * can be approximated by a polynomial algorithm with approximation ratio $2/3-\eps$. * is APX-complete, even when restricted to properly edge-colored linear forests without a $5$-vertex path, and is solvable in %time $O(m^{3/2})$ on edge-colored $m$-edge polynomial time for edge-colored forests without a $4$-vertex path. * is APX-complete, even when restricted to properly edge-colored trees without an $8$-vertex path, and is solvable in %time $O(n^{7/2})$ on edge-colored $n$-vertex polynomial time for edge-colored trees without a $7$-vertex path. * is APX-complete, even when restricted to properly edge-colored paths. These results provide a dichotomy theorem for the complexity of the problem on forests and trees in terms of forbidding paths. The latter is somewhat surprising, since, to the best of our knowledge, no (unweighted) graph problem prior to our result is known to be NP-hard for simple paths. We also address the parameterized complexity of the problem.
A New Term Rewriting Characterisation of ETIME functions
Venue: arXiv cs.LO 2013
Year: 2013

Adopting former term rewriting characterisations of polytime and exponential-time computable functions, we introduce a new reduction order, the Path Order for ETIME (POE* for short), that is sound and complete for ETIME computable functions. The proposed reduction order for ETIME makes contrasts to those related complexity classes clear.
Algorithmic Perspectives of Network Transitive Reduction Problems and their Applications to Synthesis and Analysis of Biological Networks
Venue: arXiv cs.CC 2013
Year: 2013

In this survey paper, we will present a number of core algorithmic questions concerning several transitive reduction problems on network that have applications in network synthesis and analysis involving cellular processes. Our starting point will be the so-called minimum equivalent digraph problem, a classic computational problem in combinatorial algorithms. We will subsequently consider a few non-trivial extensions or generalizations of this problem motivated by applications in systems biology. We will then discuss the applications of these algorithmic methodologies in the context of three major biological research questions: synthesizing and simplifying signal transduction networks, analyzing disease networks, and measuring redundancy of biological networks.
Lesion Border Detection in Dermoscopy Images Using Ensembles of Thresholding Methods
Venue: arXiv cs.CV 2013
Year: 2013

Dermoscopy is one of the major imaging modalities used in the diagnosis of melanoma and other pigmented skin lesions. Due to the difficulty and subjectivity of human interpretation, automated analysis of dermoscopy images has become an important research area. Border detection is often the first step in this analysis. In many cases, the lesion can be roughly separated from the background skin using a thresholding method applied to the blue channel. However, no single thresholding method appears to be robust enough to successfully handle the wide variety of dermoscopy images encountered in clinical practice. In this paper, we present an automated method for detecting lesion borders in dermoscopy images using ensembles of thresholding methods. Experiments on a difficult set of 90 images demonstrate that the proposed method is robust, fast, and accurate when compared to nine state-of-the-art methods.
CAPTCHA Based on Human Cognitive Factor
Venue: arXiv cs.HC 2013
Year: 2013

A CAPTCHA (Completely Automated Public Turing test to tell Computers and Humans Apart) is an automatic security mechanism used to determine whether the user is a human or a malicious computer program. It is a program that generates and grades tests that are human solvable, but intends to be beyond the capabilities of current computer programs. CAPTCHA should be designed to be very easy for humans but very hard for machines. Unfortunately, the existing CAPTCHA systems while trying to maximize the difficulty for automated programs to pass tests by increasing distortion or noise have consequently, made it also very difficult for potential users. To address the issue, this paper addresses an alternative form of CAPTCHA that provides a variety of questions from mathematical, logical and general problems which only human can understand and answer correctly in a given time. The proposed framework supports diversity in choosing the questions to be answered and a user-friendly framework to the users. A user-study is also conducted to judge the performance of the developed system with different background. The study shows the efficacy of the implemented system with a good level of user satisfaction over traditional CAPTCHA available today.
Distributed average tracking for multiple reference signals with general linear dynamics
Venue: arXiv cs.SY 2013
Year: 2013

This technical note studies the distributed average tracking problem for multiple time-varying signals with general linear dynamics, whose reference inputs are nonzero and not available to any agent in the network. In distributed fashion, a pair of continuous algorithms with, respectively, static and adaptive coupling strengths are designed. Based on the boundary layer concept, the proposed continuous algorithm with static coupling strengths can asymptotically track the average of the multiple reference signals without chattering phenomenon. Furthermore, for the case of algorithms with adaptive coupling strengths, the average tracking errors are uniformly ultimately bounded and exponentially converge to a small adjustable bounded set. Finally, a simulation example is presented to show the validity of the theoretical results.
Tree-width and Logspace: Determinants and Counting Euler Tours
Venue: arXiv cs.CC 2013
Year: 2013

Motivated by the recent result of [EJT10] showing that MSO properties are Logspace computable on graphs of bounded tree-width, we consider the complexity of computing the determinant of the adjacency matrix of a bounded tree-width graph and prove that it is L-complete. It is important to notice that the determinant is neither an MSO-property nor counts the number of solutions of an MSO-predicate. We extend this technique to count the number of spanning arborescences and directed Euler tours in bounded tree-width digraphs, and further to counting the number of spanning trees and the number of Euler tours in undirected graphs, all in L. Notice that undirected Euler tours are not known to be MSO-expressible and the corresponding counting problem is in fact #P-hard for general graphs. Counting undirected Euler tours in bounded tree-width graphs was not known to be polynomial time computable till very recently Chebolu et al [CCM13] gave a polynomial time algorithm for this problem (concurrently and independently of this work). Finally, we also show some linear algebraic extensions of the determinant algorithm to show how to compute the charcteristic polynomial and trace of the powers of a bounded tree-width graph in L.
Towards Connected Enterprises: The Business Network System
Venue: arXiv cs.DB 2013
Year: 2013

The discovery, representation and reconstruction of Business Networks (BN) from Network Mining (NM) raw data is a difficult problem for enterprises. This is due to huge amounts of complex business processes within and across enterprise boundaries, heterogeneous technology stacks, and fragmented data. To remain competitive, visibility into the enterprise and partner networks on different, interrelated abstraction levels is desirable. We present a novel data discovery, mining and network inference system, called Business Network System (BNS), that reconstructs the BN--integration and business process networks--from raw data, hidden in the enterprises' landscapes. BNS provides a new, declarative foundation for gathering information, defining a network model, inferring the network and check its conformance to the real-world "as-is" network. The paper covers both the foundation and the key features of BNS, including its underlying technologies, its overall system architecture, and its most interesting capabilities.
A Novel Method for Automatic Segmentation of Brain Tumors in MRI Images
Venue: arXiv cs.CV 2013
Year: 2013

The brain tumor segmentation on MRI images is a very difficult and important task which is used in surgical and medical planning and assessments. If experts do the segmentation manually with their own medical knowledge, it will be time-consuming. Therefore, researchers propose methods and systems which can do the segmentation automatically and without any interference. In this article, an unsupervised automatic method for brain tumor segmentation on MRI images is presented. In this method, at first in the pre-processing level, the extra parts which are outside the skull and don't have any helpful information are removed and then anisotropic diffusion filter with 8-connected neighborhood is applied to the MRI images to remove noise. By applying the fast bounding box(FBB) algorithm, the tumor area is displayed on the MRI image with a bounding box and the central part is selected as sample points for training of a One Class SVM classifier. A database is also provided by the Zanjan MRI Center. The MRI images are related to 10 patients who have brain tumor. 100 T2-weighted MRI images are used in this study. Experimental results show the high precision and dependability of the proposed algorithm. The results are also highly helpful for specialists and radiologists to easily estimate the size and position of a tumor.
Insight into Primal Augmented Lagrangian Multilplier Method
Venue: arXiv cs.NA 2013
Year: 2013

We provide a simplified form of Primal Augmented Lagrange Multiplier algorithm. We intend to fill the gap in the steps involved in the mathematical derivations of the algorithm so that an insight into the algorithm is made. The experiment is focused to show the reconstruction done using this algorithm.
Fully distributed optimal channel assignment for open spectrum access
Venue: arXiv cs.DC 2013
Year: 2013

In this paper we address the problem of fully distributed assignment of users to sub-bands such that the sum-rate of the system is maximized. We introduce a modified auction algorithm that can be applied in a fully distributed way using an opportunistic CSMA assignment scheme and is $ε$ optimal. We analyze the expected time complexity of the algorithm and suggest a variant to the algorithm that has lower expected complexity. We then show that in the case of i.i.d Rayleigh channels a simple greedy scheme is asymptotically optimal as $\SNR$ increases or as the number of users is increased to infinity. We conclude by providing simulated results of the suggested algorithms.
A Novel Application Licensing Framework for Mobile Cloud Environment
Venue: arXiv cs.CY 2013
Year: 2013

Mobile cloud computing is a new technology that enhances smartphone applications capabilities in terms of performance, energy efficiency, and execution support. These features are achieved via computation offloading technique that is supported by specialized mobile cloud application development models. However, the cloud-enabled applications are prone to application piracy issue for which the traditional licensing frameworks are of no use. Therefore, a new licensing framework is required to control application piracy in mobile cloud environment. This paper presents a preliminary design of a novel application licensing framework for mobile cloud environment that restricts execution of applications on unauthenticated smartphones and cloud resources.
Elastic Pathing: Your Speed is Enough to Track You
Venue: arXiv cs.CR 2013
Year: 2013

Today people increasingly have the opportunity to opt-in to "usage-based" automotive insurance programs for reducing insurance premiums. In these programs, participants install devices in their vehicles that monitor their driving behavior, which raises some privacy concerns. Some devices collect fine-grained speed data to monitor driving habits. Companies that use these devices claim that their approach is privacy-preserving because speedometer measurements do not have physical locations. However, we show that with knowledge of the user's home location, as the insurance companies have, speed data is sufficient to discover driving routes and destinations when trip data is collected over a period of weeks. To demonstrate the real-world applicability of our approach we applied our algorithm, elastic pathing, to data collected over hundreds of driving trips occurring over several months. With this data and our approach, we were able to predict trip destinations to within 250 meters of ground truth in 10% of the traces and within 500 meters in 20% of the traces. This result, combined with the amount of speed data that is being collected by insurance companies, constitutes a substantial breach of privacy because a person's regular driving pattern can be deduced with repeated examples of the same paths with just a few weeks of monitoring.
Decision Making under Uncertainty: A Quasimetric Approach
Venue: arXiv cs.AI 2013
Year: 2013

We propose a new approach for solving a class of discrete decision making problems under uncertainty with positive cost. This issue concerns multiple and diverse fields such as engineering, economics, artificial intelligence, cognitive science and many others. Basically, an agent has to choose a single or series of actions from a set of options, without knowing for sure their consequences. Schematically, two main approaches have been followed: either the agent learns which option is the correct one to choose in a given situation by trial and error, or the agent already has some knowledge on the possible consequences of his decisions; this knowledge being generally expressed as a conditional probability distribution. In the latter case, several optimal or suboptimal methods have been proposed to exploit this uncertain knowledge in various contexts. In this work, we propose following a different approach, based on the geometric intuition of distance. More precisely, we define a goal independent quasimetric structure on the state space, taking into account both cost function and transition probability. We then compare precision and computation time with classical approaches.
Mathematical analysis of a discrete fracture model coupling Darcy flow in the matrix with Darcy-Forchheimer flow in the fracture
Venue: arXiv cs.NA 2013
Year: 2013

We consider a model for flow in a porous medium with a fracture in which the flow in the fracture is governed by the Darcy-Forchheimer law while that in the surrounding matrix is governed by Darcy's law. We give an appropriate mixed, variational formulation and show existence and uniqueness of the solution. To show existence we give an analogous formulation for the model in which the Darcy-Forchheimer law is the governing equation throughout the domain. We show existence and uniqueness of the solution and show that the solution for the model with Darcy's law in the matrix is the weak limit of solutions of the model with the Darcy-Forchheimer law in the entire domain when the Forchheimer coefficient in the matrix tends toward zero.
Leaf Classification Using Shape, Color, and Texture Features
Venue: arXiv cs.CV 2013
Year: 2013

Several methods to identify plants have been proposed by several researchers. Commonly, the methods did not capture color information, because color was not recognized as an important aspect to the identification. In this research, shape and vein, color, and texture features were incorporated to classify a leaf. In this case, a neural network called Probabilistic Neural network (PNN) was used as a classifier. The experimental result shows that the method for classification gives average accuracy of 93.75% when it was tested on Flavia dataset, that contains 32 kinds of plant leaves. It means that the method gives better performance compared to the original work.
Face Verification Using Kernel Principle Component Analysis
Venue: arXiv cs.CV 2013
Year: 2013

In the beginning stage, face verification is done using easy method of geometric algorithm models, but the verification route has now developed into a scientific progress of complicated geometric representation and matching process. In modern time the skill have enhanced face detection system into the vigorous focal point. Researchers currently undergoing strong research on finding face recognition system for wider area information taken under hysterical elucidation dissimilarity. The proposed face recognition system consists of a narrative exposition indiscreet preprocessing method, a hybrid Fourier-based facial feature extraction and a score fusion scheme. We take in conventional the face detection in unlike cheer up circumstances and at unusual setting. Image processing, Image detection, Feature removal and Face detection are the methods used for Face Verification System . This paper focuses mainly on the issue of toughness to lighting variations. The proposed system has obtained an average of verification rate on Two-Dimensional images under different lightening conditions.
Price of Anarchy for Greedy Auctions
Venue: arXiv cs.GT 2014
Year: 2014

We consider auctions in which greedy algorithms, paired with first-price or critical-price payment rules, are used to resolve multi-parameter combinatorial allocation problems. We study the price of anarchy for social welfare in such auctions. We show for a variety of equilibrium concepts, including Bayes-Nash equilibrium and correlated equilibrium, the resulting price of anarchy bound is close to the approximation factor of the underlying greedy algorithm.
Improved Analysis of a Max Cut Algorithm Based on Spectral Partitioning
Venue: arXiv cs.DS 2014
Year: 2014

Trevisan [SICOMP 2012] presented an algorithm for Max-Cut based on spectral partitioning techniques. This is the first algorithm for Max-Cut with an approximation guarantee strictly larger than 1/2 that is not based on semidefinite programming. Trevisan showed that its approximation ratio is of at least 0.531. In this paper we improve this bound up to 0.614247. We also define and extend this result for the more general Maximum Colored Cut problem.