OpenRaiser/Intern-Atlas huggingface dataset:
Advanced Data Processing in the Business Network System
Venue: arXiv cs.OH 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 e.g. 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 show the query and data processing capabilities of 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. The paper covers both the foundation and the key data processing characteristics features of BNS, including its underlying technologies, its overall system architecture, and data provenance approach.
Actions in the Eye: Dynamic Gaze Datasets and Learnt Saliency Models for Visual Recognition
Venue: arXiv cs.CV 2013
Year: 2013

Systems based on bag-of-words models from image features collected at maxima of sparse interest point operators have been used successfully for both computer visual object and action recognition tasks. While the sparse, interest-point based approach to recognition is not inconsistent with visual processing in biological systems that operate in `saccade and fixate' regimes, the methodology and emphasis in the human and the computer vision communities remains sharply distinct. Here, we make three contributions aiming to bridge this gap. First, we complement existing state-of-the art large scale dynamic computer vision annotated datasets like Hollywood-2 and UCF Sports with human eye movements collected under the ecological constraints of the visual action recognition task. To our knowledge these are the first large human eye tracking datasets to be collected and made publicly available for video, vision.imar.ro/eyetracking (497,107 frames, each viewed by 16 subjects), unique in terms of their (a) large scale and computer vision relevance, (b) dynamic, video stimuli, (c) task control, as opposed to free-viewing. Second, we introduce novel sequential consistency and alignment measures, which underline the remarkable stability of patterns of visual search among subjects. Third, we leverage the significant amount of collected data in order to pursue studies and build automatic, end-to-end trainable computer vision systems based on human eye movements. Our studies not only shed light on the differences between computer vision spatio-temporal interest point image sampling strategies and the human fixations, as well as their impact for visual recognition performance, but also demonstrate that human fixations can be accurately predicted, and when used in an end-to-end automatic system, leveraging some of the advanced computer vision practice, can lead to state of the art results.
Response-Based Approachability and its Application to Generalized No-Regret Algorithms
Venue: arXiv cs.LG 2013
Year: 2013

Approachability theory, introduced by Blackwell (1956), provides fundamental results on repeated games with vector-valued payoffs, and has been usefully applied since in the theory of learning in games and to learning algorithms in the online adversarial setup. Given a repeated game with vector payoffs, a target set $S$ is approachable by a certain player (the agent) if he can ensure that the average payoff vector converges to that set no matter what his adversary opponent does. Blackwell provided two equivalent sets of conditions for a convex set to be approachable. The first (primary) condition is a geometric separation condition, while the second (dual) condition requires that the set be {\em non-excludable}, namely that for every mixed action of the opponent there exists a mixed action of the agent (a {\em response}) such that the resulting payoff vector belongs to $S$. Existing approachability algorithms rely on the primal condition and essentially require to compute at each stage a projection direction from a given point to $S$. In this paper, we introduce an approachability algorithm that relies on Blackwell's {\em dual} condition. Thus, rather than projection, the algorithm relies on computation of the response to a certain action of the opponent at each stage. The utility of the proposed algorithm is demonstrated by applying it to certain generalizations of the classical regret minimization problem, which include regret minimization with side constraints and regret minimization for global cost functions. In these problems, computation of the required projections is generally complex but a response is readily obtainable.
Information Spreading on Almost Torus Networks
Venue: arXiv cs.SI 2013
Year: 2013

Epidemic modeling has been extensively used in the last years in the field of telecommunications and computer networks. We consider the popular Susceptible-Infected-Susceptible spreading model as the metric for information spreading. In this work, we analyze information spreading on a particular class of networks denoted almost torus networks and over the lattice which can be considered as the limit when the torus length goes to infinity. Almost torus networks consist on the torus network topology where some nodes or edges have been removed. We find explicit expressions for the characteristic polynomial of these graphs and tight lower bounds for its computation. These expressions allow us to estimate their spectral radius and thus how the information spreads on these networks.
Probabilistic Spectral Sparsification In Sublinear Time
Venue: arXiv cs.DS 2013
Year: 2013

In this paper, we introduce a variant of spectral sparsification, called probabilistic $(\varepsilon,δ)$-spectral sparsification. Roughly speaking, it preserves the cut value of any cut $(S,S^{c})$ with an $1\pm\varepsilon$ multiplicative error and a $δ\left|S\right|$ additive error. We show how to produce a probabilistic $(\varepsilon,δ)$-spectral sparsifier with $O(n\log n/\varepsilon^{2})$ edges in time $\tilde{O}(n/\varepsilon^{2}δ)$ time for unweighted undirected graph. This gives fastest known sub-linear time algorithms for different cut problems on unweighted undirected graph such as - An $\tilde{O}(n/OPT+n^{3/2+t})$ time $O(\sqrt{\log n/t})$-approximation algorithm for the sparsest cut problem and the balanced separator problem. - A $n^{1+o(1)}/\varepsilon^{4}$ time approximation minimum s-t cut algorithm with an $\varepsilon n$ additive error.
A Novel Approach For Generating Face Template Using Bda
Venue: arXiv cs.CV 2013
Year: 2013

In identity management system, commonly used biometric recognition system needs attention towards issue of biometric template protection as far as more reliable solution is concerned. In view of this biometric template protection algorithm should satisfy security, discriminability and cancelability. As no single template protection method is capable of satisfying the basic requirements, a novel technique for face template generation and protection is proposed. The novel approach is proposed to provide security and accuracy in new user enrollment as well as authentication process. This novel technique takes advantage of both the hybrid approach and the binary discriminant analysis algorithm. This algorithm is designed on the basis of random projection, binary discriminant analysis and fuzzy commitment scheme. Three publicly available benchmark face databases are used for evaluation. The proposed novel technique enhances the discriminability and recognition accuracy by 80% in terms of matching score of the face images and provides high security.
A Fast and Practical Method to Estimate Volumes of Convex Polytopes
Venue: arXiv cs.CG 2013
Year: 2013

The volume is an important attribute of a convex body. In general, it is quite difficult to calculate the exact volume. But in many cases, it suffices to have an approximate value. Volume estimation methods for convex bodies have been extensively studied in theory, however, there is still a lack of practical implementations of such methods. In this paper, we present an efficient method which is based on the Multiphase Monte-Carlo algorithm to estimate volumes of convex polytopes. It uses the coordinate directions hit-and-run method, and employs a technique of reutilizing sample points. The experiments show that our method can efficiently handle instances with dozens of dimensions with high accuracy.
Speeding-Up Convergence via Sequential Subspace Optimization: Current State and Future Directions
Venue: arXiv cs.NA 2013
Year: 2013

This is an overview paper written in style of research proposal. In recent years we introduced a general framework for large-scale unconstrained optimization -- Sequential Subspace Optimization (SESOP) and demonstrated its usefulness for sparsity-based signal/image denoising, deconvolution, compressive sensing, computed tomography, diffraction imaging, support vector machines. We explored its combination with Parallel Coordinate Descent and Separable Surrogate Function methods, obtaining state of the art results in above-mentioned areas. There are several methods, that are faster than plain SESOP under specific conditions: Trust region Newton method - for problems with easily invertible Hessian matrix; Truncated Newton method - when fast multiplication by Hessian is available; Stochastic optimization methods - for problems with large stochastic-type data; Multigrid methods - for problems with nested multilevel structure. Each of these methods can be further improved by merge with SESOP. One can also accelerate Augmented Lagrangian method for constrained optimization problems and Alternating Direction Method of Multipliers for problems with separable objective function and non-separable constraints.
Band Allocation for Cognitive Radios with Buffered Primary and Secondary Users
Venue: arXiv cs.NI 2013
Year: 2013

In this paper, we study band allocation of $\mathcal{M}_s$ buffered secondary users (SUs) to $\mathcal{M}_p$ orthogonal primary licensed bands, where each primary band is assigned to one primary user (PU). Each SU is assigned to one of the available primary bands with a certain probability designed to satisfy some specified quality of service (QoS) requirements for the SUs. In the proposed system, only one SU is assigned to a particular band. The optimization problem used to obtain the stability region's envelope (closure) is shown to be a linear program. We compare the stability region of the proposed system with that of a system where each SU chooses a band randomly with some assignment probability. We also compare with a fixed (deterministic) assignment system, where only one SU is assigned to one of the primary bands all the time. We prove the advantage of the proposed system over the other systems.
Bits Through Bufferless Queues
Venue: arXiv cs.IT 2013
Year: 2013

This paper investigates the capacity of a channel in which information is conveyed by the timing of consecutive packets passing through a queue with independent and identically distributed service times. Such timing channels are commonly studied under the assumption of a work-conserving queue. In contrast, this paper studies the case of a bufferless queue that drops arriving packets while a packet is in service. Under this bufferless model, the paper provides upper bounds on the capacity of timing channels and establishes achievable rates for the case of bufferless M/M/1 and M/G/1 queues. In particular, it is shown that a bufferless M/M/1 queue at worst suffers less than 10% reduction in capacity when compared to an M/M/1 work-conserving queue.
Face Verification System based on Integral Normalized Gradient Image(INGI)
Venue: arXiv cs.CV 2013
Year: 2013

Character identification plays a vital role in the contemporary world of Image processing. It can solve many composite problems and makes humans work easier. An instance is Handwritten Character detection. Handwritten recognition is not a novel expertise, but it has not gained community notice until Now. The eventual aim of designing Handwritten Character recognition structure with an accurateness rate of 100% is pretty illusionary. Tamil Handwritten Character recognition system uses the Neural Networks to distinguish them. Neural Network and structural characteristics are used to instruct and recognize written characters. After training and testing the exactness rate reached 99%. This correctness rate is extremely high. In this paper we are exploring image processing through the Hilditch algorithm foundation and structural characteristics of a character in the image. And we recognized some character of the Tamil language, and we are trying to identify all the character of Tamil In our future works.
A Robust Password-Based Multi-Server Authentication Scheme
Venue: arXiv cs.CR 2013
Year: 2013

In 2013, Tsai et al. cryptanalyzed Yeh et al. scheme and shown that Yeh et al., scheme is vulnerable to various cryptographic attacks and proposed an improved scheme. In this poster we will show that Tsai et al., scheme is also vulnerable to undetectable online password guessing attack, on success of the attack, the adversary can perform all major cryptographic attacks. As apart of our contribution, we have proposed an improved scheme which overcomes the defects in Tsai et al. and Yeh et al. schemes.
Brain Tumor Detection Based On Symmetry Information
Venue: arXiv cs.CV 2013
Year: 2013

Advances in computing technology have allowed researchers across many fields of endeavor to collect and maintain vast amounts of observational statistical data such as clinical data, biological patient data, data regarding access of web sites, financial data, and the like. This paper addresses some of the challenging issues on brain magnetic resonance (MR) image tumor segmentation caused by the weak correlation between magnetic resonance imaging (MRI) intensity and anatomical meaning. With the objective of utilizing more meaningful information to improve brain tumor segmentation, an approach which employs bilateral symmetry information as an additional feature for segmentation is proposed. This is motivated by potential performance improvement in the general automatic brain tumor segmentation systems which are important for many medical and scientific applications
Worst-Case Optimal Tree Layout in External Memory
Venue: arXiv cs.DS 2013
Year: 2013

Consider laying out a fixed-topology tree of N nodes into external memory with block size B so as to minimize the worst-case number of block memory transfers required to traverse a path from the root to a node of depth D. We prove that the optimal number of memory transfers is $$ \cases{ \displaystyle Θ\left( {D \over \lg (1{+}B)} \right) & when $D = O(\lg N)$, \cr \displaystyle Θ\left( {\lg N \over \lg \left(1{+}{B \lg N \over D}\right)} \right) & when $D = Ω(\lg N)$ and $D = O(B \lg N)$, \cr \displaystyle Θ\left( {D \over B} \right) & when $D = Ω(B \lg N)$. } $$
Geometric Complexity Theory IV: nonstandard quantum group for the Kronecker problem
Venue: arXiv cs.CC 2013
Year: 2013

The Kronecker coefficient g_{λμν} is the multiplicity of the GL(V)\times GL(W)-irreducible V_λ\otimes W_μin the restriction of the GL(X)-irreducible X_νvia the natural map GL(V)\times GL(W) \to GL(V \otimes W), where V, W are \mathbb{C}-vector spaces and X = V \otimes W. A fundamental open problem in algebraic combinatorics is to find a positive combinatorial formula for these coefficients. We construct two quantum objects for this problem, which we call the nonstandard quantum group and nonstandard Hecke algebra. We show that the nonstandard quantum group has a compact real form and its representations are completely reducible, that the nonstandard Hecke algebra is semisimple, and that they satisfy an analog of quantum Schur-Weyl duality. Using these nonstandard objects as a guide, we follow the approach of Adsul, Sohoni, and Subrahmanyam to construct, in the case dim(V) = dim(W) =2, a representation \check{X}_νof the nonstandard quantum group that specializes to Res_{GL(V) \times GL(W)} X_νat q=1. We then define a global crystal basis +HNSTC(ν) of \check{X}_νthat solves the two-row Kronecker problem: the number of highest weight elements of +HNSTC(ν) of weight (λ,μ) is the Kronecker coefficient g_{λμν}. We go on to develop the beginnings of a graphical calculus for this basis, along the lines of the U_q(\sl_2) graphical calculus, and use this to organize the crystal components of +HNSTC(ν) into eight families. This yields a fairly simple, explicit and positive formula for two-row Kronecker coefficients, generalizing a formula of Brown, van Willigenburg, and Zabrocki. As a byproduct of the approach, we also obtain a rule for the decomposition of Res_{GL_2 \times GL_2 \rtimes §_2} X_νinto irreducibles.
Integer-Forcing Linear Receivers
Venue: arXiv cs.IT 2014
Year: 2014

Linear receivers are often used to reduce the implementation complexity of multiple-antenna systems. In a traditional linear receiver architecture, the receive antennas are used to separate out the codewords sent by each transmit antenna, which can then be decoded individually. Although easy to implement, this approach can be highly suboptimal when the channel matrix is near singular. This paper develops a new linear receiver architecture that uses the receive antennas to create an effective channel matrix with integer-valued entries. Rather than attempting to recover transmitted codewords directly, the decoder recovers integer combinations of the codewords according to the entries of the effective channel matrix. The codewords are all generated using the same linear code which guarantees that these integer combinations are themselves codewords. Provided that the effective channel is full rank, these integer combinations can then be digitally solved for the original codewords. This paper focuses on the special case where there is no coding across transmit antennas and no channel state information at the transmitter(s), which corresponds either to a multi-user uplink scenario or to single-user V-BLAST encoding. In this setting, the proposed integer-forcing linear receiver significantly outperforms conventional linear architectures such as the zero-forcing and linear MMSE receiver. In the high SNR regime, the proposed receiver attains the optimal diversity-multiplexing tradeoff for the standard MIMO channel with no coding across transmit antennas. It is further shown that in an extended MIMO model with interference, the integer-forcing linear receiver achieves the optimal generalized degrees-of-freedom.
Randomness for Free
Venue: arXiv cs.GT 2014
Year: 2014

We consider two-player zero-sum games on graphs. These games can be classified on the basis of the information of the players and on the mode of interaction between them. On the basis of information the classification is as follows: (a) partial-observation (both players have partial view of the game); (b) one-sided complete-observation (one player has complete observation); and (c) complete-observation (both players have complete view of the game). On the basis of mode of interaction we have the following classification: (a) concurrent (both players interact simultaneously); and (b) turn-based (both players interact in turn). The two sources of randomness in these games are randomness in transition function and randomness in strategies. In general, randomized strategies are more powerful than deterministic strategies, and randomness in transitions gives more general classes of games. In this work we present a complete characterization for the classes of games where randomness is not helpful in: (a) the transition function probabilistic transition can be simulated by deterministic transition); and (b) strategies (pure strategies are as powerful as randomized strategies). As consequence of our characterization we obtain new undecidability results for these games.
Analysis of Agglomerative Clustering
Venue: arXiv cs.DS 2014
Year: 2014

The diameter $k$-clustering problem is the problem of partitioning a finite subset of $\mathbb{R}^d$ into $k$ subsets called clusters such that the maximum diameter of the clusters is minimized. One early clustering algorithm that computes a hierarchy of approximate solutions to this problem (for all values of $k$) is the agglomerative clustering algorithm with the complete linkage strategy. For decades, this algorithm has been widely used by practitioners. However, it is not well studied theoretically. In this paper, we analyze the agglomerative complete linkage clustering algorithm. Assuming that the dimension $d$ is a constant, we show that for any $k$ the solution computed by this algorithm is an $O(\log k)$-approximation to the diameter $k$-clustering problem. Our analysis does not only hold for the Euclidean distance but for any metric that is based on a norm. Furthermore, we analyze the closely related $k$-center and discrete $k$-center problem. For the corresponding agglomerative algorithms, we deduce an approximation factor of $O(\log k)$ as well.
Towards Optimal Schemes for the Half-Duplex Two-Way Relay Channel
Venue: arXiv cs.IT 2014
Year: 2014

A restricted two-way communication problem in a small fully-connected network is investigated. The network consists of three nodes, all having access to a common channel with half-duplex constraint. Two nodes want to establish a dialog while the third node can assist in the bi-directional transmission process. All nodes have agreed on a transmission protocol a priori and the problem is restricted to the dialog encoders not being allowed to establish a cooperation by the use of previous receive signals. The channel is referred to as the restricted half-duplex two-way relay channel. Here the channel is defined and an outer bound on the achievable rates is derived by the application of the cut-set theorem. This shows that the problem consists of six parts. We propose a transmission protocol which takes into account all possible transmit-receive configurations of the network and performs partial decoding of the messages at the relay as well as sequential decoding at the dialog nodes. By the use of random codes and suboptimal decoders, two inner bound on the achievable rates are derived. Restricting to the suggested strategies and fixed input distributions it is argued to be possible to determine optimal transmission schemes with respect to various reasonable objectives at low complexity. In comparison to two-way communication without relay, simulations for an AWGN channel model then show that it is possible to simultaneously increase the communication rates of both dialog messages and to outperform relaying strategies that ignore an available direct path.