OpenRaiser/Intern-Atlas huggingface dataset:
Feature selection via simultaneous sparse approximation for person specific face verification
Venue: arXiv cs.CV 2011
Year: 2011

There is an increasing use of some imperceivable and redundant local features for face recognition. While only a relatively small fraction of them is relevant to the final recognition task, the feature selection is a crucial and necessary step to select the most discriminant ones to obtain a compact face representation. In this paper, we investigate the sparsity-enforced regularization-based feature selection methods and propose a multi-task feature selection method for building person specific models for face verification. We assume that the person specific models share a common subset of features and novelly reformulated the common subset selection problem as a simultaneous sparse approximation problem. To the best of our knowledge, it is the first time to apply the sparsity-enforced regularization methods for person specific face verification. The effectiveness of the proposed methods is verified with the challenging LFW face databases.
A Hybrid Global Minimization Scheme for Accurate Source Localization in Sensor Networks
Venue: arXiv cs.NI 2011
Year: 2011

We consider the localization problem of multiple wideband sources in a multi-path environment by coherently taking into account the attenuation characteristics and the time delays in the reception of the signal. Our proposed method leaves the space for unavailability of an accurate signal attenuation model in the environment by considering the model as an unknown function with reasonable prior assumptions about its functional space. Such approach is capable of enhancing the localization performance compared to only utilizing the signal attenuation information or the time delays. In this paper, the localization problem is modeled as a cost function in terms of the source locations, attenuation model parameters and the multi-path parameters. To globally perform the minimization, we propose a hybrid algorithm combining the differential evolution algorithm with the Levenberg-Marquardt algorithm. Besides the proposed combination of optimization schemes, supporting the technical details such as closed forms of cost function sensitivity matrices are provided. Finally, the validity of the proposed method is examined in several localization scenarios, taking into account the noise in the environment, the multi-path phenomenon and considering the sensors not being synchronized.
Finitely generated free Heyting algebras via Birkhoff duality and coalgebra
Venue: arXiv cs.LO 2011
Year: 2011

Algebras axiomatized entirely by rank 1 axioms are algebras for a functor and thus the free algebras can be obtained by a direct limit process. Dually, the final coalgebras can be obtained by an inverse limit process. In order to explore the limits of this method we look at Heyting algebras which have mixed rank 0-1 axiomatizations. We will see that Heyting algebras are special in that they are almost rank 1 axiomatized and can be handled by a slight variant of the rank 1 coalgebraic methods.
The effect of linguistic constraints on the large scale organization of language
Venue: arXiv cs.CL 2011
Year: 2011

This paper studies the effect of linguistic constraints on the large scale organization of language. It describes the properties of linguistic networks built using texts of written language with the words randomized. These properties are compared to those obtained for a network built over the text in natural order. It is observed that the "random" networks too exhibit small-world and scale-free characteristics. They also show a high degree of clustering. This is indeed a surprising result - one that has not been addressed adequately in the literature. We hypothesize that many of the network statistics reported here studied are in fact functions of the distribution of the underlying data from which the network is built and may not be indicative of the nature of the concerned network.
Density Evolution Analysis of Node-Based Verification-Based Algorithms in Compressed Sensing
Venue: arXiv cs.IT 2011
Year: 2011

In this paper, we present a new approach for the analysis of iterative node-based verification-based (NB-VB) recovery algorithms in the context of compressive sensing. These algorithms are particularly interesting due to their low complexity (linear in the signal dimension $n$). The asymptotic analysis predicts the fraction of unverified signal elements at each iteration $\ell$ in the asymptotic regime where $n \rightarrow \infty$. The analysis is similar in nature to the well-known density evolution technique commonly used to analyze iterative decoding algorithms. To perform the analysis, a message-passing interpretation of NB-VB algorithms is provided. This interpretation lacks the extrinsic nature of standard message-passing algorithms to which density evolution is usually applied. This requires a number of non-trivial modifications in the analysis. The analysis tracks the average performance of the recovery algorithms over the ensembles of input signals and sensing matrices as a function of $\ell$. Concentration results are devised to demonstrate that the performance of the recovery algorithms applied to any choice of the input signal over any realization of the sensing matrix follows the deterministic results of the analysis closely. Simulation results are also provided which demonstrate that the proposed asymptotic analysis matches the performance of recovery algorithms for large but finite values of $n$. Compared to the existing technique for the analysis of NB-VB algorithms, which is based on numerically solving a large system of coupled differential equations, the proposed method is much simpler and more accurate.
A Phenomenological Study on Threshold Improvement via Spatial Coupling
Venue: arXiv cs.IT 2011
Year: 2011

Kudekar et al. proved an interesting result in low-density parity-check (LDPC) convolutional codes: The belief-propagation (BP) threshold is boosted to the maximum-a-posteriori (MAP) threshold by spatial coupling. Furthermore, the authors showed that the BP threshold for code-division multiple-access (CDMA) systems is improved up to the optimal one via spatial coupling. In this letter, a phenomenological model for elucidating the essence of these phenomenon, called threshold improvement, is proposed. The main result implies that threshold improvement occurs for spatially-coupled general graphical models.
Profit-Aware Server Allocation for Green Internet Services
Venue: arXiv cs.PF 2011
Year: 2011

A server farm is examined, where a number of servers are used to offer a service to impatient customers. Every completed request generates a certain amount of profit, running servers consume electricity for power and cooling, while waiting customers might leave the system before receiving service if they experience excessive delays. A dynamic allocation policy aiming at satisfying the conflicting goals of maximizing the quality of users' experience while minimizing the cost for the provider is introduced and evaluated. The results of several experiments are described, showing that the proposed scheme performs well under different traffic conditions.
Superiority of one-way and realtime quantum machines and new directions
Venue: arXiv cs.CC 2011
Year: 2011

In automata theory, the quantum computation has been widely examined for finite state machines, known as quantum finite automata (QFAs), and less attention has been given to the QFAs augmented with counters or stacks. Moreover, to our knowledge, there is no result related to QFAs having more than one input head. In this paper, we focus on such generalizations of QFAs whose input head(s) operate(s) in one-way or realtime mode and present many superiority of them to their classical counterparts. Furthermore, we propose some open problems and conjectures in order to investigate the power of quantumness better. We also give some new results on classical computation.
Multi-linear iterative K-Sigma-semialgebras
Venue: arXiv cs.DM 2011
Year: 2011

We consider $K$-semialgebras for a commutative semiring $K$ that are at the same time $Σ$-algebras and satisfy certain linearity conditions. When each finite system of guarded polynomial fixed point equations has a unique solution over such an algebra, then we call it an iterative multi-linear $K$-$Σ$-semialgebra. Examples of such algebras include the algebras of $Σ$-tree series over an alphabet $A$ with coefficients in $K$, and the algebra of all rational tree series. We show that for many commutative semirings $K$, the rational $Σ$-tree series over $A$ with coefficients in $K$ form the free multi-linear iterative $K$-$Σ$-semialgebra on $A$.
On the Cognitive Interference Channel with Unidirectional Destination Cooperation
Venue: arXiv cs.IT 2011
Year: 2011

The cognitive interference channel with unidirectional destination cooperation (CIFC-UDC) is a cognitive interference channel (CIFC) where the cognitive (secondary) destination not only decodes the information sent from its sending dual but also helps enhance the communication of the primary user. This channel model is an extension of the original CIFC to achieve a win-win solution under the coexistence condition. From an information-theoretic perspective, the CIFC-UDC comprises a broadcast channel (BC), a relay channel (RC) and a partially cooperative relay broadcast channel (PCRBC), and can be degraded to any one of them. Our main result is the establishment of a new unified achieva-ble rate region for the CIFC-UDC which is the largest known to date and can be explicitly shown to include the previous result proposed by Chu and the largest known rate regions for the BC, the RC and the PCRBC. In addition, an interesting viewpoint on the unidirectional destination cooperation in the CIFC-UDC is discussed: to enable the decoder of the primary user to perform interference mitigation can be considered as a complementary idea to the interference mitigation via Gel'fand-Pinsker precod-ing in the CIFC proposed by Devroye et al. Henceforth, by com-bing these two ideas, the interferences caused at both the desti-nations can be alleviated. Lastly, an outer bound is presented and proved to be tight for a class of the CIFC-UDC, resulting in the characterization of the capacity region for this class.
An Approximation Algorithm for Computing Shortest Paths in Weighted 3-d Domains
Venue: arXiv cs.CG 2011
Year: 2011

We present the first polynomial time approximation algorithm for computing shortest paths in weighted three-dimensional domains. Given a polyhedral domain $\D$, consisting of $n$ tetrahedra with positive weights, and a real number $\eps\in(0,1)$, our algorithm constructs paths in $\D$ from a fixed source vertex to all vertices of $\D$, whose costs are at most $1+\eps$ times the costs of (weighted) shortest paths, in $O(\C(\D)\frac{n}{\eps^{2.5}}\log\frac{n}{\eps}\log^3\frac{1}{\eps})$ time, where $\C(\D)$ is a geometric parameter related to the aspect ratios of tetrahedra. The efficiency of the proposed algorithm is based on an in-depth study of the local behavior of geodesic paths and additive Voronoi diagrams in weighted three-dimensional domains, which are of independent interest. The paper extends the results of Aleksandrov, Maheshwari and Sack [JACM 2005] to three dimensions.
Towards Nominal Formal Languages
Venue: arXiv cs.FL 2011
Year: 2011

We introduce formal languages over infinite alphabets where words may contain binders. We define the notions of nominal language, nominal monoid, and nominal regular expressions. Moreover, we extend history-dependent automata (HD-automata) by adding stack, and study the recognisability of nominal languages.
LQG Control Approach to Gaussian Broadcast Channels with Feedback
Venue: arXiv cs.IT 2011
Year: 2011

A code for communication over the k-receiver additive white Gaussian noise broadcast channel with feedback is presented and analyzed using tools from the theory of linear quadratic Gaussian optimal control. It is shown that the performance of this code depends on the noise correlation at the receivers and it is related to the solution of a discrete algebraic Riccati equation. For the case of independent noises, the sum rate achieved by the proposed code, satisfying average power constraint P, is characterized as 1/2 log (1+P*phi), where the coefficient "phi" in the interval [1,k] quantifies the power gain due to the presence of feedback. When specialized to the case of two receivers, this includes a previous result by Elia and strictly improves upon the code of Ozarow and Leung. When the noises are correlated, the pre-log of the sum-capacity of the broadcast channel with feedback can be strictly greater than one. It is established that for all noise covariance matrices of rank r the pre-log of the sum capacity is at most k-r+1 and, conversely, there exists a noise covariance matrix of rank r for which the proposed code achieves this upper bound. This generalizes a previous result by Gastpar and Wigger for the two-receiver broadcast channel.
On the Capacity of p2p Multipoint Video Conference
Venue: arXiv cs.NI 2011
Year: 2011

In this paper, The structure of video conference is formulated and the peer-assisted distribution scheme is constructed to achieve optimal video delivery rate in each sub-conference. The capacity of conference is proposed to referee the video rate that can be supported in every possible scenario. We have proved that, in case of one user watching only one video, 5/6 is a lower bound of the capacity which is much larger than 1/2, the achievable rate of chained approach in [2]. Almost all proofs in this paper are constructive. They can be applied into real implementation directly with a few modifications.
A New Capacity Result for the Z-Gaussian Cognitive Interference Channel
Venue: arXiv cs.IT 2011
Year: 2011

This work proposes a novel outer bound for the Gaussian cognitive interference channel in strong interference at the primary receiver based on the capacity of a multi-antenna broadcast channel with degraded message set. It then shows that for the Z-channel, i.e., when the secondary receiver experiences no interference and the primary receiver experiences strong interference, the proposed outer bound not only is the tightest among known bounds but is actually achievable for sufficiently strong interference. The latter is a novel capacity result that from numerical evaluations appears to be generalizable to a larger (i.e., non-Z) class of Gaussian channels.
The Capacity of the Interference Channel with a Cognitive Relay in Very Strong Interference
Venue: arXiv cs.IT 2011
Year: 2011

The interference channel with a cognitive relay consists of a classical interference channel with two sourcedestination pairs and with an additional cognitive relay that has a priori knowledge of the sources' messages and aids in the sources' transmission. We derive a new outer bound for this channel using an argument originally devised for the "more capable" broadcast channel, and show the achievability of the proposed outer bound in the "very strong interference" regime, a class of channels where there is no loss in optimality if both destinations decode both messages. This result is analogous to the "very strong interference" capacity result for the classical interference channel and for the cognitive interference channel, and is the first capacity known capacity result for the general interference channel with a cognitive relay.
Compressive MUSIC with optimized partial support for joint sparse recovery
Venue: arXiv cs.IT 2011
Year: 2011

Multiple measurement vector (MMV) problem addresses the identification of unknown input vectors that share common sparse support. The MMV problems had been traditionally addressed either by sensor array signal processing or compressive sensing. However, recent breakthrough in this area such as compressive MUSIC (CS-MUSIC) or subspace-augumented MUSIC (SA-MUSIC) optimally combines the compressive sensing (CS) and array signal processing such that $k-r$ supports are first found by CS and the remaining $r$ supports are determined by generalized MUSIC criterion, where $k$ and $r$ denote the sparsity and the independent snapshots, respectively. Even though such hybrid approach significantly outperforms the conventional algorithms, its performance heavily depends on the correct identification of $k-r$ partial support by compressive sensing step, which often deteriorate the overall performance. The main contribution of this paper is, therefore, to show that as long as $k-r+1$ correct supports are included in any $k$-sparse CS solution, the optimal $k-r$ partial support can be found using a subspace fitting criterion, significantly improving the overall performance of CS-MUSIC. Furthermore, unlike the single measurement CS counterpart that requires infinite SNR for a perfect support recovery, we can derive an information theoretic sufficient condition for the perfect recovery using CS-MUSIC under a {\em finite} SNR scenario.
Trellis-Based Check Node Processing for Low-Complexity Nonbinary LP Decoding
Venue: arXiv cs.IT 2011
Year: 2011

Linear Programming (LP) decoding is emerging as an attractive alternative to decode Low-Density Parity-Check (LDPC) codes. However, the earliest LP decoders proposed for binary and nonbinary LDPC codes are not suitable for use at moderate and large code lengths. To overcome this problem, Vontobel et al. developed an iterative Low-Complexity LP (LCLP) decoding algorithm for binary LDPC codes. The variable and check node calculations of binary LCLP decoding algorithm are related to those of binary Belief Propagation (BP). The present authors generalized this work to derive an iterative LCLP decoding algorithm for nonbinary linear codes. Contrary to binary LCLP, the variable and check node calculations of this algorithm are in general different from that of nonbinary BP. The overall complexity of nonbinary LCLP decoding is linear in block length; however the complexity of its check node calculations is exponential in the check node degree. In this paper, we propose a modified BCJR algorithm for efficient check node processing in the nonbinary LCLP decoding algorithm. The proposed algorithm has complexity linear in the check node degree. We also introduce an alternative state metric to improve the run time of the proposed algorithm. Simulation results are presented for $(504, 252)$ and $(1008, 504)$ nonbinary LDPC codes over $\mathbb{Z}_4$.
Capacity Bounds for Multiuser Channels with Non-Causal Channel State Information at the Transmitters
Venue: arXiv cs.IT 2011
Year: 2011

In this paper, capacity inner and outer bounds are established for the multiuser channels with Channel State Information (CSI) known non-causally at the transmitters: The Multiple Access Channel (MAC), the Broadcast Channel (BC) with common information, and the Relay Channel (RC). For each channel, the actual capacity region is also derived in some special cases. Specifically, it is shown that for some deterministic models with non-causal CSI at the transmitters, similar to Costa's Gaussian channel, the availability of CSI at the deterministic receivers does not affect the capacity region.
The Capacity Region of p-Transmitter/q-Receiver Multiple-Access Channels with Common Information
Venue: arXiv cs.IT 2011
Year: 2011

This paper investigates the capacity problem for some multiple-access scenarios with cooperative transmitters. First, a general Multiple-Access Channel (MAC) with common information, i.e., a scenario where p transmitters send private messages and also a common message to q receivers and each receiver decodes all of the messages, is considered. The capacity region of the discrete memoryless channel is characterized. Then, the general Gaussian fading MAC with common information wherein partial Channel State Information (CSI) is available at the transmitters (CSIT) and perfect CSI is available at the receivers (CSIR) is investigated. A coding theorem is proved for this model that yields an exact characterization of the throughput capacity region. Finally, a two-transmitter/one-receiver Gaussian fading MAC with conferencing encoders with partial CSIT and perfect CSIR is studied and its capacity region is determined. For the Gaussian fading models with CSIR only (transmitters have no access to CSIT), some numerical examples and simulation results are provided for Rayleigh fading.
Improved Rate-Equivocation Regions for Secure Cooperative Communication
Venue: arXiv cs.IT 2011
Year: 2011

A simple four node network in which cooperation improves the information-theoretic secrecy is studied. The channel consists of two senders, a receiver, and an eavesdropper. One or both senders transmit confidential messages to the receiver, while the eavesdropper tries to decode the transmitted message. The main result is the derivation of a newly achievable rate-equivocation region that is shown to be larger than a rate-equivocation region derived by Lai and El Gamal for the relay-eavesdropper channel. When the rate of the helping interferer is zero, the new rate-equivocation region reduces to the capacity-equivocation region over the wire-tap channel, hence, the new achievability scheme can be seen as a generalization of a coding scheme proposed by Csiszar and Korner. This result can naturally be combined with a rate-equivocation region given by Tang et al. (for the interference assisted secret communication), yielding an even larger achievable rate-equivocation region.
On the Hairpin Incompletion
Venue: arXiv cs.FL 2011
Year: 2011

Hairpin completion and its variant called bounded hairpin completion are operations on formal languages, inspired by a hairpin formation in molecular biology. Another variant called hairpin lengthening has been recently introduced and studied on the closure properties and algorithmic problems concerning several families of languages. In this paper, we introduce a new operation of this kind, called hairpin incompletion which is not only an extension of bounded hairpin completion, but also a restricted (bounded) variant of hairpin lengthening. Further, the hairpin incompletion operation provides a formal language theoretic framework that models a bio-molecular technique nowadays known as Whiplash PCR. We study the closure properties of language families under both the operation and its iterated version. We show that a family of languages closed under intersection with regular sets, concatenation with regular sets, and finite union is closed under one-sided iterated hairpin incompletion, and that a family of languages containing all linear languages and closed under circular permutation, left derivative and substitution is also closed under iterated hairpin incompletion.
On Multiple Hypothesis Testing with Rejection Option
Venue: arXiv cs.IT 2011
Year: 2011

We study the problem of multiple hypothesis testing (HT) in view of a rejection option. That model of HT has many different applications. Errors in testing of M hypotheses regarding the source distribution with an option of rejecting all those hypotheses are considered. The source is discrete and arbitrarily varying (AVS). The tradeoffs among error probability exponents/reliabilities associated with false acceptance of rejection decision and false rejection of true distribution are investigated and the optimal decision strategies are outlined. The main result is specialized for discrete memoryless sources (DMS) and studied further. An interesting insight that the analysis implies is the phenomenon (comprehensible in terms of supervised/unsupervised learning) that in optimal discrimination within M hypothetical distributions one permits always lower error than in deciding to decline the set of hypotheses. Geometric interpretations of the optimal decision schemes are given for the current and known bounds in multi-HT for AVS's.