OpenRaiser/Intern-Atlas huggingface dataset:
Large Scale Spectral Clustering Using Approximate Commute Time Embedding
Venue: arXiv cs.LG 2012
Year: 2012

Spectral clustering is a novel clustering method which can detect complex shapes of data clusters. However, it requires the eigen decomposition of the graph Laplacian matrix, which is proportion to $O(n^3)$ and thus is not suitable for large scale systems. Recently, many methods have been proposed to accelerate the computational time of spectral clustering. These approximate methods usually involve sampling techniques by which a lot information of the original data may be lost. In this work, we propose a fast and accurate spectral clustering approach using an approximate commute time embedding, which is similar to the spectral embedding. The method does not require using any sampling technique and computing any eigenvector at all. Instead it uses random projection and a linear time solver to find the approximate embedding. The experiments in several synthetic and real datasets show that the proposed approach has better clustering quality and is faster than the state-of-the-art approximate spectral clustering methods.
Grassmannian Differential Limited Feedback for Interference Alignment
Venue: arXiv cs.IT 2012
Year: 2012

Channel state information (CSI) in the interference channel can be used to precode, align, and reduce the dimension of interference at the receivers, to achieve the channel's maximum multiplexing gain, through what is known as interference alignment. Most interference alignment algorithms require knowledge of all the interfering channels to compute the alignment precoders. CSI, considered available at the receivers, can be shared with the transmitters via limited feedback. When alignment is done by coding over frequency extensions in a single antenna system, the required CSI lies on the Grassmannian manifold and its structure can be exploited in feedback. Unfortunately, the number of channels to be shared grows with the square of the number of users, creating too much overhead with conventional feedback methods. This paper proposes Grassmannian differential feedback to reduce feedback overhead by exploiting both the channel's temporal correlation and Grassmannian structure. The performance of the proposed algorithm is characterized both analytically and numerically as a function of channel length, mobility, and the number of feedback bits. The main conclusions are that the proposed feedback strategy allows interference alignment to perform well over a wide range of Doppler spreads, and to approach perfect CSI performance in slowly varying channels. Numerical results highlight the trade-off between the frequency of feedback and the accuracy of individual feedback updates.
On the Critical Delays of Mobile Networks under Lévy Walks and Lévy Flights
Venue: arXiv cs.NI 2012
Year: 2012

Delay-capacity tradeoffs for mobile networks have been analyzed through a number of research work. However, Lévy mobility known to closely capture human movement patterns has not been adopted in such work. Understanding the delay-capacity tradeoff for a network with Lévy mobility can provide important insights into understanding the performance of real mobile networks governed by human mobility. This paper analytically derives an important point in the delay-capacity tradeoff for Lévy mobility, known as the critical delay. The critical delay is the minimum delay required to achieve greater throughput than what conventional static networks can possibly achieve (i.e., $O(1/\sqrt{n})$ per node in a network with $n$ nodes). The Lévy mobility includes Lévy flight and Lévy walk whose step size distributions parametrized by $α\in (0,2]$ are both heavy-tailed while their times taken for the same step size are different. Our proposed technique involves (i) analyzing the joint spatio-temporal probability density function of a time-varying location of a node for Lévy flight and (ii) characterizing an embedded Markov process in Lévy walk which is a semi-Markov process. The results indicate that in Lévy walk, there is a phase transition such that for $α\in (0,1)$, the critical delay is always $Θ(n^{1/2})$ and for $α\in [1,2]$ it is $Θ(n^{\fracα{2}})$. In contrast, Lévy flight has the critical delay $Θ(n^{\fracα{2}})$ for $α\in(0,2]$.
Wireless Capacity and Admission Control in Cognitive Radio
Venue: arXiv cs.DS 2012
Year: 2012

We give algorithms with constant-factor performance guarantees for several capacity and throughput problems in the SINR model. The algorithms are all based on a novel LP formulation for capacity problems. First, we give a new constant-factor approximation algorithm for selecting the maximum subset of links that can be scheduled simultaneously, under any non-decreasing and sublinear power assignment. For the case of uniform power, we extend this to the case of variable QoS requirements and link-dependent noise terms. Second, we approximate a problem related to cognitive radio: find a maximum set of links that can be simultaneously scheduled without affecting a given set of previously assigned links. Finally, we obtain constant-factor approximation of weighted capacity under linear power assignment.
Efficient High-Dimensional Inference in the Multiple Measurement Vector Problem
Venue: arXiv cs.IT 2012
Year: 2012

In this work, a Bayesian approximate message passing algorithm is proposed for solving the multiple measurement vector (MMV) problem in compressive sensing, in which a collection of sparse signal vectors that share a common support are recovered from undersampled noisy measurements. The algorithm, AMP-MMV, is capable of exploiting temporal correlations in the amplitudes of non-zero coefficients, and provides soft estimates of the signal vectors as well as the underlying support. Central to the proposed approach is an extension of recently developed approximate message passing techniques to the amplitude-correlated MMV setting. Aided by these techniques, AMP-MMV offers a computational complexity that is linear in all problem dimensions. In order to allow for automatic parameter tuning, an expectation-maximization algorithm that complements AMP-MMV is described. Finally, a detailed numerical study demonstrates the power of the proposed approach and its particular suitability for application to high-dimensional problems.
Directed Steiner Tree and the Lasserre Hierarchy
Venue: arXiv cs.DS 2012
Year: 2012

The goal for the Directed Steiner Tree problem is to find a minimum cost tree in a directed graph G=(V,E) that connects all terminals X to a given root r. It is well known that modulo a logarithmic factor it suffices to consider acyclic graphs where the nodes are arranged in L <= log |X| levels. Unfortunately the natural LP formulation has a |X|^(1/2) integrality gap already for 5 levels. We show that for every L, the O(L)-round Lasserre Strengthening of this LP has integrality gap O(L log |X|). This provides a polynomial time |X|^{epsilon}-approximation and a O(log^3 |X|) approximation in O(n^{log |X|) time, matching the best known approximation guarantee obtained by a greedy algorithm of Charikar et al.
Membership(s) and compliance(s) with class-based graphs
Venue: arXiv cs.SI 2012
Year: 2012

Besides the need for a better understanding of networks, there is a need for prescriptive models and tools to specify requirements concerning networks and their associated graph representations. We propose class-based graphs as a means to specify requirements concerning object-based graphs. Various variants of membership are proposed as special relations between class-based and object-based graphs at the local level, while various variants of compliance are proposed at the global level.
Energy-aware scheduling under reliability and makespan constraints
Venue: arXiv cs.DS 2012
Year: 2012

We consider a task graph mapped on a set of homogeneous processors. We aim at minimizing the energy consumption while enforcing two constraints: a prescribed bound on the execution time (or makespan), and a reliability threshold. Dynamic voltage and frequency scaling (DVFS) is an approach frequently used to reduce the energy consumption of a schedule, but slowing down the execution of a task to save energy is decreasing the reliability of the execution. In this work, to improve the reliability of a schedule while reducing the energy consumption, we allow for the re-execution of some tasks. We assess the complexity of the tri-criteria scheduling problem (makespan, reliability, energy) of deciding which task to re-execute, and at which speed each execution of a task should be done, with two different speed models: either processors can have arbitrary speeds (continuous model), or a processor can run at a finite number of different speeds and change its speed during a computation (VDD model). We propose several novel tri-criteria scheduling heuristics under the continuous speed model, and we evaluate them through a set of simulations. The two best heuristics turn out to be very efficient and complementary.
Solving Dense Generalized Eigenproblems on Multi-threaded Architectures
Venue: arXiv cs.PF 2012
Year: 2012

We compare two approaches to compute a portion of the spectrum of dense symmetric definite generalized eigenproblems: one is based on the reduction to tridiagonal form, and the other on the Krylov-subspace iteration. Two large-scale applications, arising in molecular dynamics and material science, are employed to investigate the contributions of the application, architecture, and parallelism of the method to the performance of the solvers. The experimental results on a state-of-the-art 8-core platform, equipped with a graphics processing unit (GPU), reveal that in real applications, iterative Krylov-subspace methods can be a competitive approach also for the solution of dense problems.
Betweenness Centrality as a Driver of Preferential Attachment in the Evolution of Research Collaboration Networks
Venue: arXiv cs.SI 2012
Year: 2012

We analyze whether preferential attachment in scientific coauthorship networks is different for authors with different forms of centrality. Using a complete database for the scientific specialty of research about "steel structures," we show that betweenness centrality of an existing node is a significantly better predictor of preferential attachment by new entrants than degree or closeness centrality. During the growth of a network, preferential attachment shifts from (local) degree centrality to betweenness centrality as a global measure. An interpretation is that supervisors of PhD projects and postdocs broker between new entrants and the already existing network, and thus become focal to preferential attachment. Because of this mediation, scholarly networks can be expected to develop differently from networks which are predicated on preferential attachment to nodes with high degree centrality.
Bayesian Estimation of a Gaussian source in Middleton's Class-A Impulsive Noise
Venue: arXiv cs.IT 2012
Year: 2012

The paper focuses on minimum mean square error (MMSE) Bayesian estimation for a Gaussian source impaired by additive Middleton's Class-A impulsive noise. In addition to the optimal Bayesian estimator, the paper considers also the soft-limiter and the blanker, which are two popular suboptimal estimators characterized by very low complexity. The MMSE-optimum thresholds for such suboptimal estimators are obtained by practical iterative algorithms with fast convergence. The paper derives also the optimal thresholds according to a maximum-SNR (MSNR) criterion, and establishes connections with the MMSE criterion. Furthermore, closed form analytic expressions are derived for the MSE and the SNR of all the suboptimal estimators, which perfectly match simulation results. Noteworthy, these results can be applied to characterize the receiving performance of any multicarrier system impaired by a Gaussian-mixture noise, such as asymmetric digital subscriber lines (ADSL) and power-line communications (PLC).
Hardness of Mastermind
Venue: arXiv cs.GT 2012
Year: 2012

Mastermind is a popular board game released in 1971, where a codemaker chooses a secret pattern of colored pegs, and a codebreaker has to guess it in several trials. After each attempt, the codebreaker gets a response from the codemaker containing some information on the number of correctly guessed pegs. The search space is thus reduced at each turn, and the game continues until the codebreaker is able to find the correct code, or runs out of trials. In this paper we study several variations of #MSP, the problem of computing the size of the search space resulting from a given (possibly fictitious) sequence of guesses and responses. Our main contribution is a proof of the #P-completeness of #MSP under parsimonious reductions, which settles an open problem posed by Stuckman and Zhang in 2005, concerning the complexity of deciding if the secret code is uniquely determined by the previous guesses and responses. Similarly, #MSP stays #P-complete under Turing reductions even with the promise that the search space has at least k elements, for any constant k. (In a regular game of Mastermind, k=1.) All our hardness results hold even in the most restrictive setting, in which there are only two available peg colors, and also if the codemaker's responses contain less information, for instance like in the so-called single-count (black peg) Mastermind variation.
Uniqueness Analysis of Non-Unitary Matrix Joint Diagonalization
Venue: arXiv cs.IT 2012
Year: 2012

Matrix Joint Diagonalization (MJD) is a powerful approach for solving the Blind Source Separation (BSS) problem. It relies on the construction of matrices which are diagonalized by the unknown demixing matrix. Their joint diagonalizer serves as a correct estimate of this demixing matrix only if it is uniquely determined. Thus, a critical question is under what conditions a joint diagonalizer is unique. In the present work we fully answer this question about the identifiability of MJD based BSS approaches and provide a general result on uniqueness conditions of matrix joint diagonalization. It unifies all existing results which exploit the concepts of non-circularity, non-stationarity, non-whiteness, and non-Gaussianity. As a corollary, we propose a solution for complex BSS, which can be formulated in a closed form in terms of an eigenvalue and a singular value decomposition of two matrices.
On the Complexity of Approximate Sum of Sorted List
Venue: arXiv cs.DS 2012
Year: 2012

We consider the complexity for computing the approximate sum $a_1+a_2+...+a_n$ of a sorted list of numbers $a_1\le a_2\le ...\le a_n$. We show an algorithm that computes an $(1+ε)$-approximation for the sum of a sorted list of nonnegative numbers in an $O({1\over ε}\min(\log n, {\log ({x_{max}\over x_{min}})})\cdot (\log {1\over ε}+\log\log n))$ time, where $x_{max}$ and $x_{min}$ are the largest and the least positive elements of the input list, respectively. We prove a lower bound $Ω(\min(\log n,\log ({x_{max}\over x_{min}}))$ time for every O(1)-approximation algorithm for the sum of a sorted list of nonnegative elements. We also show that there is no sublinear time approximation algorithm for the sum of a sorted list that contains at least one negative number.
Generalized Thresholding and Online Sparsity-Aware Learning in a Union of Subspaces
Venue: arXiv cs.IT 2012
Year: 2012

This paper studies a sparse signal recovery task in time-varying (time-adaptive) environments. The contribution of the paper to sparsity-aware online learning is threefold; first, a Generalized Thresholding (GT) operator, which relates to both convex and non-convex penalty functions, is introduced. This operator embodies, in a unified way, the majority of well-known thresholding rules which promote sparsity. Second, a non-convexly constrained, sparsity-promoting, online learning scheme, namely the Adaptive Projection-based Generalized Thresholding (APGT), is developed that incorporates the GT operator with a computational complexity that scales linearly to the number of unknowns. Third, the novel family of partially quasi-nonexpansive mappings is introduced as a functional analytic tool for treating the GT operator. By building upon the rich fixed point theory, the previous class of mappings helps us, also, to establish a link between the GT operator and a union of linear subspaces; a non-convex object which lies at the heart of any sparsity promoting technique, batch or online. Based on such a functional analytic framework, a convergence analysis of the APGT is provided. Furthermore, extensive experiments suggest that the APGT exhibits competitive performance when compared to computationally more demanding alternatives, such as the sparsity-promoting Affine Projection Algorithm (APA)- and Recursive Least Squares (RLS)-based techniques.
Non-Malleable Extractors, Two-Source Extractors and Privacy Amplification
Venue: arXiv cs.CR 2012
Year: 2012

Dodis and Wichs introduced the notion of a non-malleable extractor to study the problem of privacy amplification with an active adversary. A non-malleable extractor is a much stronger version of a strong extractor. Previously, there are only two known constructions of non-malleable extractors. Both constructions only work for (n, k)-sources with k>n/2. Interestingly, both constructions are also two-source extractors. In this paper, we present a strong connection between non-malleable extractors and two-source extractors. The first part of the connection shows that non-malleable extractors can be used to construct two-source extractors. With appropriate parameters the resulted two-source extractor beats the best known construction of two-source extractors. This partially explains why previous constructions of non-malleable extractors only work for sources with entropy rate >1/2, and why explicit non-malleable extractors for small min-entropy may be hard to get. The second part of the connection shows that certain two-source extractors can be used to construct non-malleable extractors. Using this connection, we obtain the first construction of non-malleable extractors for k < n/2. Specifically, we give an unconditional construction for min-entropy k=(1/2-δ)n for some constant δ>0, and a conditional (semi-explicit) construction that can potentially achieve k=αn for any constant α>0. Finally, despite the lack of explicit non-malleable extractors for arbitrarily linear entropy, we give the first 2-round privacy amplification protocol with asymptotically optimal entropy loss and communication complexity for (n, k) sources with k=αn for any constant α>0. This dramatically improves previous results and answers an open problem in \cite{DLWZ11}.
Concentration of Measure Inequalities for Toeplitz Matrices with Applications
Venue: arXiv cs.IT 2012
Year: 2012

We derive Concentration of Measure (CoM) inequalities for randomized Toeplitz matrices. These inequalities show that the norm of a high-dimensional signal mapped by a Toeplitz matrix to a low-dimensional space concentrates around its mean with a tail probability bound that decays exponentially in the dimension of the range space divided by a quantity which is a function of the signal. For the class of sparse signals, the introduced quantity is bounded by the sparsity level of the signal. However, we observe that this bound is highly pessimistic for most sparse signals and we show that if a random distribution is imposed on the non-zero entries of the signal, the typical value of the quantity is bounded by a term that scales logarithmically in the ambient dimension. As an application of the CoM inequalities, we consider Compressive Binary Detection (CBD).
On Weak Odd Domination and Graph-based Quantum Secret Sharing
Venue: arXiv cs.CC 2012
Year: 2012

A weak odd dominated (WOD) set in a graph is a subset B of vertices for which there exists a distinct set of vertices C such that every vertex in B has an odd number of neighbors in C. We point out the connections of weak odd domination with odd domination, [sigma,rho]-domination, and perfect codes. We introduce bounds on κ(G), the maximum size of WOD sets of a graph G, and on κ'(G), the minimum size of non WOD sets of G. Moreover, we prove that the corresponding decision problems are NP-complete. The study of weak odd domination is mainly motivated by the design of graph-based quantum secret sharing protocols: a graph G of order n corresponds to a secret sharing protocol which threshold is κ_Q(G) = max(κ(G), n-κ'(G)). These graph-based protocols are very promising in terms of physical implementation, however all such graph-based protocols studied in the literature have quasi-unanimity thresholds (i.e. κ_Q(G)=n-o(n) where n is the order of the graph G underlying the protocol). In this paper, we show using probabilistic methods, the existence of graphs with smaller κ_Q (i.e. κ_Q(G)< 0.811n where n is the order of G). We also prove that deciding for a given graph G whether κ_Q(G)< k is NP-complete, which means that one cannot efficiently double check that a graph randomly generated has actually a κ_Q smaller than 0.811n.
Jointly Predicting Links and Inferring Attributes using a Social-Attribute Network (SAN)
Venue: arXiv cs.SI 2012
Year: 2012

The effects of social influence and homophily suggest that both network structure and node attribute information should inform the tasks of link prediction and node attribute inference. Recently, Yin et al. proposed Social-Attribute Network (SAN), an attribute-augmented social network, to integrate network structure and node attributes to perform both link prediction and attribute inference. They focused on generalizing the random walk with restart algorithm to the SAN framework and showed improved performance. In this paper, we extend the SAN framework with several leading supervised and unsupervised link prediction algorithms and demonstrate performance improvement for each algorithm on both link prediction and attribute inference. Moreover, we make the novel observation that attribute inference can help inform link prediction, i.e., link prediction accuracy is further improved by first inferring missing attributes. We comprehensively evaluate these algorithms and compare them with other existing algorithms using a novel, large-scale Google+ dataset, which we make publicly available.
Stochastic Geometry based Medium Access Games in Mobile Ad hoc Networks
Venue: arXiv cs.GT 2012
Year: 2012

This paper studies the performance of Mobile Ad hoc Networks (MANETs) when the nodes, that form a Poisson point process, selfishly choose their Medium Access Probability (MAP). We consider goodput and delay as the performance metric that each node is interested in optimizing taking into account the transmission energy costs. We introduce a pricing scheme based on the transmission energy requirements and compute the symmetric Nash equilibria of the game in closed form. It is shown that by appropriately pricing the nodes, the selfish behavior of the nodes can be used to achieve the social optimum at equilibrium. The Price of Anarchy is then analyzed for these games. For the game with delay based utility, we bound the price of anarchy and study the effect of the price factor. For the game with goodput based utility, it is shown that price of anarchy is infinite at the price factor that achieves the global optima.
Filtrations of Formal Languages by Arithmetic Progressions
Venue: arXiv cs.FL 2012
Year: 2012

A filtration of a formal language L by a sequence s maps L to the set of words formed by taking the letters of words of L indexed only by s. We consider the languages resulting from filtering by all arithmetic progressions. If L is regular, it is easy to see that only finitely many distinct languages result. By contrast, there exist CFL's that give infinitely many distinct languages as a result. We use our technique to show that the operation diag, which extracts the diagonal of words of square length arranged in a square array, preserves regularity but does not preserve context-freeness.