OpenRaiser/Intern-Atlas huggingface dataset:
Robust Phase Retrieval and Super-Resolution from One Bit Coded Diffraction Patterns
Venue: arXiv cs.IT 2014
Year: 2014

In this paper we study a realistic setup for phase retrieval, where the signal of interest is modulated or masked and then for each modulation or mask a diffraction pattern is collected, producing a coded diffraction pattern (CDP) [CLM13]. We are interested in the setup where the resolution of the collected CDP is limited by the Fraunhofer diffraction limit of the imaging system. We investigate a novel approach based on a geometric quantization scheme of phase-less linear measurements into (one-bit) coded diffraction patterns, and a corresponding recovery scheme. The key novelty in this approach consists in comparing pairs of coded diffractions patterns across frequencies: the one bit measurements obtained rely on the order statistics of the un-quantized measurements rather than their values . This results in a robust phase recovery, and unlike currently available methods, allows to efficiently perform phase recovery from measurements affected by severe (possibly unknown) non linear, rank preserving perturbations, such as distortions. Another important feature of this approach consists in the fact that it enables also super-resolution and blind-deconvolution, beyond the diffraction limit of a given imaging system.
Improvements on the accelerated integer GCD algorithm
Venue: arXiv cs.DC 2014
Year: 2014

The present paper analyses and presents several improvements to the algorithm for finding the $(a,b)$-pairs of integers used in the $k$-ary reduction of the right-shift $k$-ary integer GCD algorithm. While the worst-case complexity of Weber's "Accelerated integer GCD algorithm" is $\cOł(\log_ϕ(k)^2\r)$, we show that the worst-case number of iterations of the while loop is exactly $\tfrac 12 ł\lfloor \log_ϕ(k)\r\rfloor$, where $ϕ:= \tfrac 12 ł(1+\sqrt{5}\r)$.\par We suggest improvements on the average complexity of the latter algorithm and also present two new faster residual algorithms: the sequential and the parallel one. A lower bound on the probability of avoiding the while loop in our parallel residual algorithm is also given.
Modeling sequential data using higher-order relational features and predictive training
Venue: arXiv cs.LG 2014
Year: 2014

Bi-linear feature learning models, like the gated autoencoder, were proposed as a way to model relationships between frames in a video. By minimizing reconstruction error of one frame, given the previous frame, these models learn "mapping units" that encode the transformations inherent in a sequence, and thereby learn to encode motion. In this work we extend bi-linear models by introducing "higher-order mapping units" that allow us to encode transformations between frames and transformations between transformations. We show that this makes it possible to encode temporal structure that is more complex and longer-range than the structure captured within standard bi-linear models. We also show that a natural way to train the model is by replacing the commonly used reconstruction objective with a prediction objective which forces the model to correctly predict the evolution of the input multiple steps into the future. Learning can be achieved by back-propagating the multi-step prediction through time. We test the model on various temporal prediction tasks, and show that higher-order mappings and predictive training both yield a significant improvement over bi-linear models in terms of prediction accuracy.
Animation of 3D Human Model Using Markerless Motion Capture Applied To Sports
Venue: arXiv cs.GR 2014
Year: 2014

Markerless motion capture is an active research in 3D virtualization. In proposed work we presented a system for markerless motion capture for 3D human character animation, paper presents a survey on motion and skeleton tracking techniques which are developed or are under development. The paper proposed a method to transform the motion of a performer to a 3D human character (model), the 3D human character performs similar movements as that of a performer in real time. In the proposed work, human model data will be captured by Kinect camera, processed data will be applied on 3D human model for animation. 3D human model is created using open source software (MakeHuman). Anticipated dataset for sport activity is considered as input which can be applied to any HCI application.
Enhancing Human Aspect of Software Engineering using Bayesian Classifier
Venue: arXiv cs.SE 2014
Year: 2014

IT industries in current scenario have to struggle effectively in terms of cost, quality, service or innovation for their subsistence in the global market. Due to the swift transformation of technology, software industries owe to manage a large set of data having precious information hidden. Data mining technique enables one to effectively cope with this hidden information where it can be applied to code optimization, fault prediction and other domains which modulates the success nature of software projects. Additionally, the efficiency of the product developed further depends upon the quality of the project personnel. The position of the paper therefore is to explore potentials of project personnel in terms of their competency and skill set and its influence on quality of project. The above mentioned objective is accomplished using a Bayesian classifier in order to capture the pattern of human performance. By this means, the hidden and valuable knowledge discovered in the related databases will be summarized in the statistical structure. This mode of predictive study enables the project managers to reduce the failure ratio to a significant level and improve the performance of the project using the right choice of project personnel.
An evaluation of keyword extraction from online communication for the characterisation of social relations
Venue: arXiv cs.SI 2014
Year: 2014

The set of interpersonal relationships on a social network service or a similar online community is usually highly heterogenous. The concept of tie strength captures only one aspect of this heterogeneity. Since the unstructured text content of online communication artefacts is a salient source of information about a social relationship, we investigate the utility of keywords extracted from the message body as a representation of the relationship's characteristics as reflected by the conversation topics. Keyword extraction is performed using standard natural language processing methods. Communication data and human assessments of the extracted keywords are obtained from Facebook users via a custom application. The overall positive quality assessment provides evidence that the keywords indeed convey relevant information about the relationship.
E-BLOW: E-Beam Lithography Overlapping aware Stencil Planning for MCC System
Venue: arXiv cs.AR 2014
Year: 2014

Electron beam lithography (EBL) is a promising maskless solution for the technology beyond 14nm logic node. To overcome its throughput limitation, recently the traditional EBL system is extended into MCC system. %to further improve the throughput. In this paper, we present E-BLOW, a tool to solve the overlapping aware stencil planning (OSP) problems in MCC system. E-BLOW is integrated with several novel speedup techniques, i.e., successive relaxation, dynamic programming and KD-Tree based clustering, to achieve a good performance in terms of runtime and solution quality. Experimental results show that, compared with previous works, E-BLOW demonstrates better performance for both conventional EBL system and MCC system.
Layout decomposition for triple patterning lithography
Venue: arXiv cs.AR 2014
Year: 2014

As minimum feature size and pitch spacing further decrease, triple patterning lithography (TPL) is a possible 193nm extension along the paradigm of double patterning lithography (DPL). However, there is very little study on TPL layout decomposition. In this paper, we show that TPL layout decomposition is a more difficult problem than that for DPL. We then propose a general integer linear programming formulation for TPL layout decomposition which can simultaneously minimize conflict and stitch numbers. Since ILP has very poor scalability, we propose three acceleration techniques without sacrificing solution quality: independent component computation, layout graph simplification, and bridge computation. For very dense layouts, even with these speedup techniques, ILP formulation may still be too slow. Therefore, we propose a novel vector programming formulation for TPL decomposition, and solve it through effective semidefinite programming (SDP) approximation. Experimental results show that the ILP with acceleration techniques can reduce 82% runtime compared to the baseline ILP. Using SDP based algorithm, the runtime can be further reduced by 42% with some tradeoff in the stitch number (reduced by 7%) and the conflict (9% more). However, for very dense layouts, SDP based algorithm can achieve 140x speed-up even compared with accelerated ILP.
Coalitional Games with Overlapping Coalitions for Interference Management in Small Cell Networks
Venue: arXiv cs.GT 2014
Year: 2014

In this paper, we study the problem of cooperative interference management in an OFDMA two-tier small cell network. In particular, we propose a novel approach for allowing the small cells to cooperate, so as to optimize their sum-rate, while cooperatively satisfying their maximum transmit power constraints. Unlike existing work which assumes that only disjoint groups of cooperative small cells can emerge, we formulate the small cells' cooperation problem as a coalition formation game with overlapping coalitions. In this game, each small cell base station can choose to participate in one or more cooperative groups (or coalitions) simultaneously, so as to optimize the tradeoff between the benefits and costs associated with cooperation. We study the properties of the proposed overlapping coalition formation game and we show that it exhibits negative externalities due to interference. Then, we propose a novel decentralized algorithm that allows the small cell base stations to interact and self-organize into a stable overlapping coalitional structure. Simulation results show that the proposed algorithm results in a notable performance advantage in terms of the total system sum-rate, relative to the noncooperative case and the classical algorithms for coalitional games with non-overlapping coalitions.
Performance of Social Network Sensors During Hurricane Sandy
Venue: arXiv cs.SI 2014
Year: 2014

Information flow during catastrophic events is a critical aspect of disaster management. Modern communication platforms, in particular online social networks, provide an opportunity to study such flow, and a mean to derive early-warning sensors, improving emergency preparedness and response. Performance of the social networks sensor method, based on topological and behavioural properties derived from the "friendship paradox", is studied here for over 50 million Twitter messages posted before, during, and after Hurricane Sandy. We find that differences in user's network centrality effectively translate into moderate awareness advantage (up to 26 hours); and that geo-location of users within or outside of the hurricane-affected area plays significant role in determining the scale of such advantage. Emotional response appears to be universal regardless of the position in the network topology, and displays characteristic, easily detectable patterns, opening a possibility of implementing a simple "sentiment sensing" technique to detect and locate disasters.
Large Cuts with Local Algorithms on Triangle-Free Graphs
Venue: arXiv cs.DC 2014
Year: 2014

We study the problem of finding large cuts in $d$-regular triangle-free graphs. In prior work, Shearer (1992) gives a randomised algorithm that finds a cut of expected size $(1/2 + 0.177/\sqrt{d})m$, where $m$ is the number of edges. We give a simpler algorithm that does much better: it finds a cut of expected size $(1/2 + 0.28125/\sqrt{d})m$. As a corollary, this shows that in any $d$-regular triangle-free graph there exists a cut of at least this size. Our algorithm can be interpreted as a very efficient randomised distributed algorithm: each node needs to produce only one random bit, and the algorithm runs in one synchronous communication round. This work is also a case study of applying computational techniques in the design of distributed algorithms: our algorithm was designed by a computer program that searched for optimal algorithms for small values of $d$.
Étude cognitive des processus de construction d'une requête dans un système de gestion de connaissances médicales
Venue: arXiv cs.IR 2014
Year: 2014

This article presents the Cogni-CISMeF project, which aims at improving medical information search in the CISMeF system (Catalog and Index of French-language health resources) by including a conversational agent to interact with the user in natural language. To study the cognitive processes involved during the information search, a bottom-up methodology was adopted. Experimentation has been set up to obtain human dialogs between a user (playing the role of patient) dealing with medical information search and a CISMeF expert refining the request. The analysis of these dialogs underlined the use of discursive evidence: vocabulary, reformulation, implicit or explicit expression of user intentions, conversational sequences, etc. A model of artificial agent is proposed. It leads the user in its information search by proposing to him examples, assistance and choices. This model was implemented and integrated in the CISMeF system. ---- Cet article décrit le projet Cogni-CISMeF qui propose un module de dialogue Homme-Machine à intégrer dans le système d'indexation de connaissances médicales CISMeF (Catalogue et Index des Sites Médicaux Francophones). Nous avons adopté une démarche de modélisation cognitive en procédant à un recueil de corpus de dialogues entre un utilisateur (jouant le rôle d'un patient) désirant une information médicale et un expert CISMeF af inant cette demande pour construire la requête. Nous avons analysé la structure des dialogues ainsi obtenus et avons étudié un certain nombre d'indices discursifs : vocabulaire employé, marques de reformulation, commentaires méta et épilinguistiques, expression implicite ou explicite des intentions de l'utilisateur, enchaînement conversationnel, etc. De cette analyse, nous avons construit un modèle d'agent artificiel doté de capacités cognitives capables d'aider l'utilisateur dans sa tâche de recherche d'information. Ce modèle a été implémenté et intégré dans le système CISMeF.
GPU acceleration of Newton's method for large systems of polynomial equations in double double and quad double arithmetic
Venue: arXiv cs.DC 2014
Year: 2014

In order to compensate for the higher cost of double double and quad double arithmetic when solving large polynomial systems, we investigate the application of NVIDIA Tesla K20C general purpose graphics processing unit. The focus on this paper is on Newton's method, which requires the evaluation of the polynomials, their derivatives, and the solution of a linear system to compute the update to the current approximation for the solution. The reverse mode of algorithmic differentiation for a product of variables is rewritten in a binary tree fashion so all threads in a block can collaborate in the computation. For double arithmetic, the evaluation and differentiation problem is memory bound, whereas for complex quad double arithmetic the problem is compute bound. With acceleration we can double the dimension and get results that are twice as accurate in about the same time.
Cooperative Set Aggregation for Multiple Lagrangian Systems
Venue: arXiv cs.SY 2014
Year: 2014

In this paper, we study the cooperative set tracking problem for a group of Lagrangian systems. Each system observes a convex set as its local target. The intersection of these local sets is the group aggregation target. We first propose a control law based on each system's own target sensing and information exchange with neighbors. With necessary connectivity for both cases of fixed and switching communication graphs, multiple Lagrangian systems are shown to achieve rendezvous on the intersection of all the local target sets while the vectors of generalized coordinate derivatives are driven to zero. Then, we introduce the collision avoidance control term into set aggregation control to ensure group dispersion. By defining an ultimate bound on the final generalized coordinate between each system and the intersection of all the local target sets, we show that multiple Lagrangian systems approach a bounded region near the intersection of all the local target sets while the collision avoidance is guaranteed during the movement. In addition, the vectors of generalized coordinate derivatives of all the mechanical systems are shown to be driven to zero. Simulation results are given to validate the theoretical results.
Optimal Gossip with Direct Addressing
Venue: arXiv cs.DS 2014
Year: 2014

Gossip algorithms spread information by having nodes repeatedly forward information to a few random contacts. By their very nature, gossip algorithms tend to be distributed and fault tolerant. If done right, they can also be fast and message-efficient. A common model for gossip communication is the random phone call model, in which in each synchronous round each node can PUSH or PULL information to or from a random other node. For example, Karp et al. [FOCS 2000] gave algorithms in this model that spread a message to all nodes in $Θ(\log n)$ rounds while sending only $O(\log \log n)$ messages per node on average. Recently, Avin and Elsässer [DISC 2013], studied the random phone call model with the natural and commonly used assumption of direct addressing. Direct addressing allows nodes to directly contact nodes whose ID (e.g., IP address) was learned before. They show that in this setting, one can "break the $\log n$ barrier" and achieve a gossip algorithm running in $O(\sqrt{\log n})$ rounds, albeit while using $O(\sqrt{\log n})$ messages per node. We study the same model and give a simple gossip algorithm which spreads a message in only $O(\log \log n)$ rounds. We also prove a matching $Ω(\log \log n)$ lower bound which shows that this running time is best possible. In particular we show that any gossip algorithm takes with high probability at least $0.99 \log \log n$ rounds to terminate. Lastly, our algorithm can be tweaked to send only $O(1)$ messages per node on average with only $O(\log n)$ bits per message. Our algorithm therefore simultaneously achieves the optimal round-, message-, and bit-complexity for this setting. As all prior gossip algorithms, our algorithm is also robust against failures. In particular, if in the beginning an oblivious adversary fails any $F$ nodes our algorithm still, with high probability, informs all but $o(F)$ surviving nodes.
Analysis of Non-Coherent Joint-Transmission Cooperation in Heterogeneous Cellular Networks
Venue: arXiv cs.IT 2014
Year: 2014

Base station (BS) cooperation is set to play a key role in managing interference in dense heterogeneous cellular networks (HCNs). Non-coherent joint transmission (JT) is particularly appealing due to its low complexity, smaller overhead, and ability for load balancing. However, a general analysis of this technique is difficult mostly due to the lack of tractable models. This paper addresses this gap and presents a tractable model for analyzing non-coherent JT in HCNs, while incorporating key system parameters such as user-centric BS clustering and channel-dependent cooperation activation. Assuming all BSs of each tier follow a stationary Poisson point process, the coverage probability for non-coherent JT is derived. Using the developed model, it is shown that for small cooperative clusters of small-cell BSs, non-coherent JT by small cells provides spectral efficiency gains without significantly increasing cell load. Further, when cooperation is aggressively triggered intra-cluster frequency reuse within small cells is favorable over intra-cluster coordinated scheduling.
Direction Finding Algorithms with Joint Iterative Subspace Optimization
Venue: arXiv cs.DS 2014
Year: 2014

In this paper, a reduced-rank scheme with joint iterative optimization is presented for direction of arrival estimation. A rank-reduction matrix and an auxiliary reduced-rank parameter vector are jointly optimized to calculate the output power with respect to each scanning angle. Subspace algorithms to estimate the rank-reduction matrix and the auxiliary vector are proposed. Simulations are performed to show that the proposed algorithms achieve an enhanced performance over existing algorithms in the studied scenarios.
Sparsification and subexponential approximation
Venue: arXiv cs.CC 2014
Year: 2014

Instance sparsification is well-known in the world of exact computation since it is very closely linked to the Exponential Time Hypothesis. In this paper, we extend the concept of sparsification in order to capture subexponential time approximation. We develop a new tool for inapproximability, called approximation preserving sparsification and use it in order to get strong inapproximability results in subexponential time for several fundamental optimization problems as Max Independent Set, Min Dominating Set, Min Feedback Vertex Set, and Min Set Cover.
GLOW: A global router for low-power thermal-reliable interconnect synthesis using photonic wavelength multiplexing
Venue: arXiv cs.AR 2014
Year: 2014

In this paper, we examine the integration potential and explore the design space of low power thermal reliable on-chip interconnect synthesis featuring nanophotonics Wavelength Division Multiplexing (WDM). With the recent advancements, it is foreseen that nanophotonics holds the promise to be employed for future on-chip data signalling due to its unique power efficiency, signal delay and huge multiplexing potential. However, there are major challenges to address before feasible on-chip integration could be reached. In this paper, we present GLOW, a hybrid global router to provide low power opto-electronic interconnect synthesis under the considerations of thermal reliability and various physical design constraints such as optical power, delay and signal quality. GLOW is evaluated with testing cases derived from ISPD07-08 global routing benchmarks. Compared with a greedy approach, GLOW demonstrates around 23%-50% of total optical power reduction, revealing great potential of on-chip WDM interconnect synthesis.
Formal Specification Language Based IaaS Cloud Workload Regression Analysis
Venue: arXiv cs.DC 2014
Year: 2014

Cloud Computing is an emerging area for accessing computing resources. In general, Cloud service providers offer services that can be clustered into three categories: SaaS, PaaS and IaaS. This paper discusses the Cloud workload analysis. The efficient Cloud workload resource mapping technique is proposed. This paper aims to provide a means of understanding and investigating IaaS Cloud workloads and the resources. In this paper, regression analysis is used to analyze the Cloud workloads and identifies the relationship between Cloud workloads and available resources. The effective organization of dynamic nature resources can be done with the help of Cloud workloads. Till Cloud workload is considered a vital talent, the Cloud resources cannot be consumed in an effective style. The proposed technique has been validated by Z Formal specification language. This approach is effective in minimizing the cost and submission burst time of Cloud workloads.