Mathematics from the arXiv

curated by isomorphismes

[arxiv-math]

Authors: Joseph Salmon, Rebecca Willett, Ery Arias-Castro

This paper describes a simple image noise removal method which combines a preprocessing step with the Yaroslavsky filter for strong numerical, visual, and theoretical performance on a broad class of images. The framework developed is a two-stage approach. In the first stage the image is filtered with a classical denoising method (e.g., wavelet or curvelet thresholding). In the second stage a modification of the Yaroslavsky filter is performed on the original noisy image, where the weights of the filters are governed by pixel similarities in the denoised image from the first stage. Similar prefiltering ideas have proved effective previously in the literature, and this paper provides theoretical guarantees and important insight into why prefiltering can be effective. Empirically, this simple approach achieves very good performance for cartoon images, and can be computed much more quickly than current patch-based denoising algorithms.

[arxiv-math]

Authors: Mingyu Guo, Vincent Conitzer

We study a more powerful variant of false-name manipulation in Internet auctions: an agent can submit multiple false-name bids, but then, once the allocation and payments have been decided, withdraw some of her false-name identities (have some of her false-name identities refuse to pay). While these withdrawn identities will not obtain the items they won, their initial presence may have been beneficial to the agent's other identities. We define a mechanism to be false-name-proof with withdrawal (FNPW) if the aforementioned manipulation is never beneficial. FNPW is a stronger condition than false-name-proofness (FNP).

[arxiv-math]

Authors: Amol Sasane

The classical Shannon sampling theorem states that a signal f with Fourier transform F in L^2(R) having its support contained in (-\pi,\pi) can be recovered from the sequence of samples (f(n))_{n in Z} via f(t)=\sum_{n in Z} f(n) (sin(\pi (t -n)))/(\pi (t-n)) (t in R). In this article we prove a generalization of this result under the assumption that F is a compactly supported distribution with its support contained in (-\pi,\pi).

[arxiv-math]

Authors: Pierre-Malo Deni'elou, Nobuko Yoshida, Andi Bejleri, Raymond Hu

For many application-level distributed protocols and parallel algorithms, the set of participants, the number of messages or the interaction structure are only known at run-time. This paper proposes a dependent type theory for multiparty sessions which can statically guarantee type-safe, deadlock-free multiparty interactions among processes whose specifications are parameterised by indices. We use the primitive recursion operator from G"odel's System T to express a wide range of communication patterns while keeping type checking decidable. To type individual distributed processes, a parameterised global type is projected onto a generic generator which represents a class of all possible end-point types. We prove the termination of the type-checking algorithm in the full system with both multiparty session types and recursive types. We illustrate our type theory through non-trivial programming and verification examples taken from parallel algorithms and Web services usecases.

[arxiv-math]

Authors: Lev Kazakovtsev

In this paper, we consider an approach to the parallelizing of the algorithms realizing the modified probability changigng method with adaptation and partial rollback procedure for constrained pseudo-Boolean optimization problems. Existing optimization algorithms are adapted for the shared memory and clusters (PVM library). The parallel efficiency is estimated for the lagre-scale non-linear pseudo-Boolean optimization problems with linear constraints. Initially designed for unconstrained optimization, the probability changing method (MIVER) allows us finding the approximate solution of different linear and non-linear pseudo-Boolean optimization problems with constraints. Although, in case of large-scale problems, the computational demands are also very high and the precision of the result depends on the time spent. In case of the constrained optimization problem, even the search of any permissibly solution can take very large computational resources. The rapid development of the parallel processor systems which are often implemented even in the computer systems designed for home use allows to reduce significantly the time spent to find the acceptable solution with a speed-up close to ideal.

[arxiv-math]

Authors: Zai Yang, Lihua Xie, Cishen Zhang

Sparse Bayesian learning (SBL) is a popular approach to sparse signal recovery in compressed sensing (CS). In SBL, the signal sparsity information is exploited by assuming a sparsity-inducing prior for the signal that is then estimated using Bayesian inference. In this paper, a new sparsity-inducing prior is introduced and efficient algorithms are developed for signal recovery. The main algorithm is shown to produce a sparser solution than existing SBL methods while preserving their desirable properties. Numerical simulations with one-dimensional synthetic signals and two-dimensional images verify our analysis and show that for sparse signals the proposed algorithm outperforms its SBL peers in both the signal recovery accuracy and computational speed. Its improved performance is also demonstrated in comparison with other state-of-the-art methods in CS.

[arxiv-math]

Authors: Srinivasan Venkatramanan, Anurag Kumar

We consider a setting in which a single item of content (such as a song or a video clip) is disseminated in a population of mobile nodes by opportunistic copying when pairs of nodes come in radio contact. We propose and study models that capture the joint evolution of the population of nodes interested in the content (referred to as destinations), and the population of nodes that possess the content. The evolution of interest in the content is captured using an influence spread model and the content spread occurs via epidemic copying. Nodes not yet interested in the content are called relays; the influence spread process converts relays into destinations. We consider the decentralized setting, where interest in the content and the spread of the content evolve by pairwise interactions between the mobiles. We derive fluid limits for the joint evolution models and obtain optimal policies for copying to relay nodes in order to deliver content to a desired fraction of destinations. We prove that a time-threshold policy is optimal while copying to relays. We then provide insights into the effects of various system parameters on the co-evolution model through simulations.

[arxiv-math]

Authors: Derek Groen, Stefan J. Zasada, Peter V. Coveney

Multiscale and multiphysics applications are becoming increasingly common, and many researchers focus on combining existing models to construct combined multiscale models. Here we present a concise review of multiscale applications and their source communities. We assess and compare the methods they use to construct their multiscale models and we characterize areas where inter-disciplinary multiscale collaboration could be particularly beneficial. We conclude that multiscale computing has become increasingly popular in recent years, that different communities adopt very different organizational approaches, and that simulations on a length scale of a few metres and a time scale of a few hours can be found in many of the multiscale research domains. Sharing multiscale methods specifically geared towards these scales between communities may therefore be particularly beneficial.

[arxiv-math]

Authors: Pierre Olivier (Lab-STICC), Jalil Boukhobza (Lab-STICC)

Nowadays, the use of embedded operating systems in different embedded projects is subject to a tremendous growth. Embedded Linux is becoming one of those most popular EOSs due to its modularity, efficiency, reliability, and cost. One way to make it hard real-time is to include a real-time kernel like Xenomai. One of the key characteristics of a Real-Time Operating System (RTOS) is its ability to meet execution time deadlines deterministically. So, the more precise and flexible the time management can be, the better it can handle efficiently the determinism for different embedded applications. RTOS time precision is characterized by a specific periodic interrupt service controlled by a software time manager. The smaller the period of the interrupt, the better the precision of the RTOS, the more it overloads the CPU, and though reduces the overall efficiency of the RTOS. In this paper, we propose to drastically reduce these overheads by migrating the time management service of Xenomai into a configurable hardware component to relieve the CPU. The hardware component is implemented in a Field Programmable Gate Array coupled to the CPU. This work was achieved in a Master degree project where students could apprehend many fields of embedded systems: RTOS programming, hardware design, performance evaluation, etc.

[arxiv-math]

Authors: Muneendra Ojha

In this paper, we propose to develop service model architecture by merging multi-agentsystems and semantic web technology. The proposed architecture works in two stages namely, Query Identification and Solution Development. A person referred to as customer will submit the problem details or requirements which will be referred to as a query. Anyone who can provide a service will need to register with the registrar module of the architecture. Services can be anything ranging from expert consultancy in the field of agriculture to academic research, from selling products to manufacturing goods, from medical help to legal issues or even providing logistics. Query submitted by customer is first parsed and then iteratively understood with the help of domain experts and the customer to get a precise set of properties. Query thus identified will be solved again with the help of intelligent agent systems which will search the semantic web for all those who can find or provide a solution. A workable solution workflow is created and then depending on the requirements, using the techniques of negotiation or auctioning, solution is implemented to complete the service for customer. This part is termed as solution development. In this service oriented architecture, we first try to analyze the complex set of user requirements then try to provide best possible solution in an optimized way by combining better information searches through semantic web and better workflow provisioning using multi agent systems.

[arxiv-math]

Authors: Samson Abramsky

Our aim in this paper is to point out a surprising formal connection, between two topics which seem on face value to have nothing to do with each other: relational database theory, and the study of non-locality and contextuality in the foundations of quantum mechanics. We shall show that there is a remarkably direct correspondence between central results such as Bell's theorem in the foundations of quantum mechanics, and questions which arise naturally and have been well-studied in relational database theory.

[arxiv-math]

Authors: Kee-Hoon Kim, Hyun-Seung Joo, Jong-Seon No, Dong-Joon Shin

There are many selected mapping (SLM) schemes to reduce the peak-to-average power ratio (PAPR) of orthogonal frequency division multiplexing (OFDM) signals. Beginning with the conventional SLM scheme, there have been proposed many low-complexity SLM schemes including Lim's, Wang's, and Baxely's SLM schemes typically. In this paper, we propose an adaptive generation (AG) method of OFDM signals in SLM schemes. By generating the alternative OFDM signals adaptively, unnecessary computational complexity of SLM schemes can be removed without any degradation of their PAPR reduction performance. In this paper, we apply the AG method to various SLM schemes which are the conventional SLM scheme and its low-complexity versions such as Lim's, Wang's, and Baxely's SLM schemes. Of course, the AG method can be applied to most of existing SLM schemes easily. The numerical results show that the AG method can reduce their computational complexity substantially.

[arxiv-math]

Authors: Janardan Misra

This is a companion draft to the paper 'Software Clustering: Unifying Syntactic and Semantic Features', 19th Working Conference on Reverse Engineering (WCRE 2012). It discusses software clustering process in detail, which appeared in the paper in an abridged form. It also contains certain additional process steps which were not covered in the WCRE paper. The clustering process is described for applications with Java source-code. However, as argued in the WCRE paper, it can be seamlessly adapted to many other programming paradigms.

[arxiv-math]

Authors: Piyus Kedia, Sorav Bansal, Deepak Deshpande, Sreekanth Iyer

Cloud Computing has emerged as a successful computing paradigm for efficiently utilizing managed compute infrastructure such as high speed rack-mounted servers, connected with high speed networking, and reliable storage. Usually such infrastructure is dedicated, physically secured and has reliable power and networking infrastructure. However, much of our idle compute capacity is present in unmanaged infrastructure like idle desktops, lab machines, physically distant server machines, and laptops. We present a scheme to utilize this idle compute capacity on a best-effort basis and provide high availability even in face of failure of individual components or facilities.

We run virtual machines on the commodity infrastructure and present a cloud interface to our end users. The primary challenge is to maintain availability in the presence of node failures, network failures, and power failures. We run multiple copies of a Virtual Machine (VM) redundantly on geographically dispersed physical machines to achieve availability. If one of the running copies of a VM fails, we seamlessly switchover to another running copy. We use Virtual Machine Record/Replay capability to implement this redundancy and switchover. In current progress, we have implemented VM Record/Replay for uniprocessor machines over Linux/KVM and are currently working on VM Record/Replay on shared-memory multiprocessor machines. We report initial experimental results based on our implementation.

[arxiv-math]

Authors: Pierre Olivier (Lab-STICC), Jalil Boukhobza (Lab-STICC), Eric Senn (Lab-STICC)

Due to its attractive characteristics in terms of performance, weight and power consumption, NAND flash memory became the main non volatile memory (NVM) in embedded systems. Those NVMs also present some specific characteristics/constraints: good but asymmetric I/O performance, limited lifetime, write/erase granularity asymmetry, etc. Those peculiarities are either managed in hardware for flash disks (SSDs, SD cards, USB sticks, etc.) or in software for raw embedded flash chips. When managed in software, flash algorithms and structures are implemented in a specific flash file system (FFS). In this paper, we present a performance study of the most widely used FFSs in embedded Linux: JFFS2, UBIFS,and YAFFS. We show some very particular behaviors and large performance disparities for tested FFS operations such as mounting, copying, and searching file trees, compression, etc.

[arxiv-math]

Authors: Pierre Olivier (Lab-STICC), Jalil Boukhobza (Lab-STICC), Eric Senn (Lab-STICC)

Today, flash memory are strongly used in the embedded system domain. NAND flash memories are the building block of main secondary storage systems. Such memories present many benefits in terms of data density, I/O performance, shock resistance and power consumption. Nevertheless, flash does not come without constraints: the write / erase granularity asymmetry and the limited lifetime bring the need for specific management. This can be done through the operating system using dedicated Flash File Systems (FFSs). In this document, we present general concepts about FFSs, and implementations example that are JFFS2, YAFFS2 and UBIFS, the most commonly used flash file systems. Then we give performance evaluation results for these FFSs.

[arxiv-math]

Authors: Yahia Benmoussa (Lab-STICC), Jalil Boukhobza (Lab-STICC), Yassine Hadjadj Aoul (INRIA - IRISA), Loïc Lagadec (Lab-STICC), Djamel Benazzouz (LMSS)

Nowadays, the use of mobile applications and terminals faces fundamental challenges related to energy constraint. This is due to the limited battery lifetime as compared to the increasing hardware evolution. Video streaming is one of the most energy consuming applications in a mobile system because of its intensive use of bandwidth, memory and processing power. In this work, we aim to propose a methodology for building and validating a high level global power consumption model including a hardware and software elements. Our approach is based on exploiting the interactions between power consumption sub-models of standalone systems in the perspective to build more accurate global model. The interactions are studied within the exclusive context of video streaming applications that are one of the most used mobile applications.