A game theoretic approach for feature clustering and its application to feature selection

In this paper, we develop a game theoretic approach for clustering features in a learning problem. Feature clustering can serve as an important preprocessing step in many problems such as feature selection, dimensionality reduction, etc. In this approach, we view features as rational players of a coalitional game where they form coalitions (or clusters) among themselves in order to maximize their individual payoffs. We show how Nash Stable Partition (NSP), a well known concept in the coalitional game theory, provides a natural way of clustering features. Through this approach, one can obtain some desirable properties of the clusters by choosing appropriate payoff functions. For a small number of features, the NSP based clustering can be found by solving an integer linear program (ILP). However, for large number of features, the ILP based approach does not scale well and hence we propose a hierarchical approach. Interestingly, a key result that we prove on the equivalence between a k-size NSP of a coalitional game and minimum k-cut of an appropriately constructed graph comes in handy for large scale problems. In this paper, we use feature selection problem (in a classification setting) as a running example to illustrate our approach. We conduct experiments to illustrate the efficacy of our approach.

An algorithm to find all palindromic sequences in proteins

A palindrome is a set of characters that reads the same forwards and backwards. Since the discovery of palindromic peptide sequences two decades ago, little effort has been made to understand its structural, functional and evolutionary significance. Therefore, in view of this, an algorithm has been developed to identify all perfect palindromes (excluding the palindromic subset and tandem repeats) in a single protein sequence. The proposed algorithm does not impose any restriction on the number of residues to be given in the input sequence. This avant-garde algorithm will aid in the identification of palindromic peptide sequences of varying lengths in a single protein sequence.

Capacity of fading gaussian channel with an energy harvesting sensor node

Network life time maximization is becoming an important design goal in wireless sensor networks. Energy harvesting has recently become a preferred choice for achieving this goal as it provides near perpetual operation. We study such a sensor node with an energy harvesting source and compare various architectures by which the harvested energy is used. We find its Shannon capacity when it is transmitting its observations over a fading AWGN channel with perfect/no channel state information provided at the transmitter. We obtain an achievable rate when there are inefficiencies in energy storage and the capacity when energy is spent in activities other than transmission.

Modeling the effect of transmission errors on TCP controlled transfers over infrastructure 802.11 wireless LANs

There have been several studies on the performance of TCP controlled transfers over an infrastructure IEEE 802.11 WLAN, assuming perfect channel conditions. In this paper, we develop an analytical model for the throughput of TCP controlled file transfers over the IEEE 802.11 DCF with different packet error probabilities for the stations, accounting for the effect of packet drops on the TCP window. Our analysis proceeds by combining two models: one is an extension of the usual TCP-over-DCF model for an infrastructure WLAN, where the throughput of a station depends on the probability that the head-of-the-line packet at the Access Point belongs to that station; the second is a model for the TCP window process for connections with different drop probabilities. Iterative calculations between these models yields the head-of-the-line probabilities, and then, performance measures such as the throughputs and packet failure probabilities can be derived. We find that, due to MAC layer retransmissions, packet losses are rare even with high channel error probabilities and the stations obtain fair throughputs even when some of them have packet error probabilities as high as 0.1 or 0.2. For some restricted settings we are also able to model tail-drop loss at the AP. Although involving many approximations, the model captures the system behavior quite accurately, as compared with simulations.

Optimal forwarding in delay tolerant networks with multiple destinations

We study the trade-off between delivery delay and energy consumption in a delay tolerant network in which a message (or a file) has to be delivered to each of several destinations by epidemic relaying. In addition to the destinations, there are several other nodes in the network that can assist in relaying the message. We first assume that, at every instant, all the nodes know the number of relays carrying the packet and the number of destinations that have received the packet. We formulate the problem as a controlled continuous time Markov chain and derive the optimal closed loop control (i.e., forwarding policy). However, in practice, the intermittent connectivity in the network implies that the nodes may not have the required perfect knowledge of the system state. To address this issue, we obtain an ODE (i.e., fluid) approximation for the optimally controlled Markov chain. This fluid approximation also yields an asymptotically optimal open loop policy. Finally, we evaluate the performance of the deterministic policy over finite networks. Numerical results show that this policy performs close to the optimal closed loop policy.

Cooperative distributed sequential spectrum sensing

We consider cooperative spectrum sensing for cognitive radios. We develop an energy efficient detector with low detection delay using sequential hypothesis testing. Sequential Probability Ratio Test (SPRT) is used at both the local nodes and the fusion center. We also analyse the performance of this algorithm and compare with the simulations. Modelling uncertainties in the distribution parameters are considered. Slow fading with and without perfect channel state information at the cognitive radios is taken into account.

Cooperative distributed sequential spectrum sensing

We consider cooperative spectrum sensing for cognitive radios. We develop an energy efficient detector with low detection delay using sequential hypothesis testing. Sequential Probability Ratio Test (SPRT) is used at both the local nodes and the fusion center. We also analyse the performance of this algorithm and compare with the simulations. Modelling uncertainties in the distribution parameters are considered. Slow fading with and without perfect channel state information at the cognitive radios is taken into account.

Design and Application of a new Multiscale Multidirectional Non-subsampled Filter Bank

We propose a new method for design of computationally efficient nonsubsampled multiscale multidirectional filter bank with perfect reconstruction (PR). This filter bank is composed of two nonsubsampled filter banks, for multiscale decomposition and for directional expansion. For multiscale decomposition, we transform the 1-D equivalent subband filters directly into 2-D equivalent subband filters. The computational cost is considerably reduced by avoiding the computation of 2-D convolutions. The multidirectional decomposition utilizes fan filters. A new method for design of 2-D zero phase FIR fan filter transformation function is developed. This method also aids the transformation of a 1-D filter bank to a 2-D multidirectional filter bank. The potential application of the proposed filter bank is illustrated by comparing the image denoising performance of the proposed filter bank with other design method that exist in available literature.

Structured Dispersion Matrices From Division Algebra Codes for Space-Time Shift Keying

We propose a novel method of constructing Dispersion Matrices (DM) for Coherent Space-Time Shift Keying (CSTSK) relying on arbitrary PSK signal sets by exploiting codes from division algebras. We show that classic codes from Cyclic Division Algebras (CDA) may be interpreted as DMs conceived for PSK signal sets. Hence various benefits of CDA codes such as their ability to achieve full diversity are inherited by CSTSK. We demonstrate that the proposed CDA based DMs are capable of achieving a lower symbol error ratio than the existing DMs generated using the capacity as their optimization objective function for both perfect and imperfect channel estimation.

Adaptive constellation rotation scheme for two-user fading MAC with quantized fade state feedback

With no Channel State Information (CSI) at the users, transmission over the two-user Gaussian Multiple Access Channel with fading and finite constellation at the input, will have high error rates due to multiple access interference (MAI). However, perfect CSI at the users is an unrealistic assumption in the wireless scenario, as it would involve extremely large feedback overheads. In this paper we propose a scheme which removes the adverse effect of MAI using only quantized knowledge of fade state at the transmitters such that the associated overhead is nominal. One of the users rotates its constellation relative to the other without varying the transmit power to adapt to the existing channel conditions, in order to meet certain predetermined minimum Euclidean distance requirement in the equivalent constellation at the destination. The optimal rotation scheme is described for the case when both the users use symmetric M-PSK constellations at the input, where M = 2(gimel), gimel being a positive integer. The strategy is illustrated by considering the example where both the users use QPSK signal sets at the input. The case when the users use PSK constellations of different sizes is also considered. It is shown that the proposed scheme has considerable better error performance compared to the conventional non-adaptive scheme, at the cost of a feedback overhead of just log log(2) (M-2/8 - M/4 + 2)] + 1 bits, for the M-PSK case.

Tiling stencil computations to maximize parallelism

Most stencil computations allow tile-wise concurrent start, i.e., there always exists a face of the iteration space and a set of tiling hyperplanes such that all tiles along that face can be started concurrently. This provides load balance and maximizes parallelism. However, existing automatic tiling frameworks often choose hyperplanes that lead to pipelined start-up and load imbalance. We address this issue with a new tiling technique that ensures concurrent start-up as well as perfect load-balance whenever possible. We first provide necessary and sufficient conditions on tiling hyperplanes to enable concurrent start for programs with affine data accesses. We then provide an approach to find such hyperplanes. Experimental evaluation on a 12-core Intel Westmere shows that our code is able to outperform a tuned domain-specific stencil code generator by 4% to 27%, and previous compiler techniques by a factor of 2x to 10.14x.

Conformational Diversity in Contryphans from Conus Venom: cis-trans Isomerisation and Aromatic/Proline Interactions in the 23-Membered Ring of a 7-Residue Peptide Disulfide Loop

Conformational diversity or shapeshifting in cyclic peptide natural products can, in principle, confer a single molecular entity with the property of binding to multiple receptors. Conformational equilibria have been probed in the contryphans, which are peptides derived from Conus venom possessing a 23-membered cyclic disulfide moiety. The natural sequences derived from Conus inscriptus, GCV(D)LYPWC* (In936) and Conus loroisii, GCP(D)WDPWC* (Lo959) differ in the number of proline residues within the macrocyclic ring. Structural characterisation of distinct conformational states arising from cis-trans equilibria about Xxx-Pro bonds is reported. Isomerisation about the C2-P3 bond is observed in the case of Lo959 and about the Y5-P6 bond in In936. Evidence is presented for as many as four distinct species in the case of the synthetic analogue V3P In936. The Tyr-Pro-Trp segment in In936 is characterised by distinct sidechain orientations as a consequence of aromatic/proline interactions as evidenced by specific sidechain-sidechain nuclear Overhauser effects and ring current shifted proton chemical shifts. Molecular dynamics simulations suggest that Tyr5 and Trp7 sidechain conformations are correlated and depend on the geometry of the Xxx-Pro bond. Thermodynamic parameters are derived for the cis trans equilibrium for In936. Studies on synthetic analogues provide insights into the role of sequence effects in modulating isomerisation about Xxx-Pro bonds.

Graphene-MoS2 hybrid structures for multifunctional photoresponsive memory devices

Combining the electronic properties of graphene(1,2) and molybdenum disulphide (MoS2)(3-6) in hybrid heterostructures offers the possibility to create devices with various functionalities. Electronic logic and memory devices have already been constructed from graphene-MoS2 hybrids(7,8), but they do not make use of the photosensitivity of MoS2, which arises from its optical-range bandgap(9). Here, we demonstrate that graphene-on-MoS2 binary heterostructures display remarkable dual optoelectronic functionality, including highly sensitive photodetection and gate-tunable persistent photoconductivity. The responsivity of the hybrids was found to be nearly 1 x 10(10) A W-1 at 130 K and 5 x 10(8) A W-1 at room temperature, making them the most sensitive graphene-based photodetectors. When subjected to time-dependent photoillumination, the hybrids could also function as a rewritable optoelectronic switch or memory, where the persistent state shows almost no relaxation or decay within experimental timescales, indicating near-perfect charge retention. These effects can be quantitatively explained by gate-tunable charge exchange between the graphene and MoS2 layers, and may lead to new graphene-based optoelectronic devices that are naturally scalable for large-area applications at room temperature.

Antenna selection for time-varying channels based on slepian subspace projections

Single receive antenna selection (AS) allows single-input single-output (SISO) systems to retain the diversity benefits of multiple antennas with minimum hardware costs. We propose a single receive AS method for time-varying channels, in which practical limitations imposed by next-generation wireless standards such as training, packetization and antenna switching time are taken into account. The proposed method utilizes low-complexity subspace projection techniques spanned by discrete prolate spheroidal (DPS) sequences. It only uses Doppler bandwidth knowledge, and does not need detailed correlation knowledge. Results show that the proposed AS method outperforms ideal conventional SISO systems with perfect CSI but no AS at the receiver and AS using the conventional Fourier estimation/prediction method. A closed-form expression for the symbol error probability (SEP) of phase-shift keying (MPSK) with symbol-by-symbol receive AS is derived.

Channel estimation at the transmitter in a reciprocal MIMO spatial multiplexing system

This paper considers the problem of channel estimation at the transmitter in a spatial multiplexing-based Time Division Duplex (TDD) Multiple Input Multiple Output (MIMO) system with perfect CSIR. A novel channel-dependent Reverse Channel Training (RCT) sequence is proposed, using which the transmitter estimates the beamforming vectors for forward link data transmission. This training sequence is designed based on the following two metrics: (i) a capacity lower bound, and (ii) the mean square error in the estimate. The performance of the proposed training scheme is analyzed and is shown to significantly outperform the conventional orthogonal RCT sequence. Also, in the case where the transmitter uses water-filling power allocation for data transmission, a novel RCT sequence is proposed and optimized with respect to the MSE in estimating the transmit covariance matrix.