Interval Data Classification under Partial Information: A Chance-Constraint Approach

This paper presents a Chance-constraint Programming approach for constructing maximum-margin classifiers which are robust to interval-valued uncertainty in training examples. The methodology ensures that uncertain examples are classified correctly with high probability by employing chance-constraints. The main contribution of the paper is to pose the resultant optimization problem as a Second Order Cone Program by using large deviation inequalities, due to Bernstein. Apart from support and mean of the uncertain examples these Bernstein based relaxations make no further assumptions on the underlying uncertainty. Classifiers built using the proposed approach are less conservative, yield higher margins and hence are expected to generalize better than existing methods. Experimental results on synthetic and real-world datasets show that the proposed classifiers are better equipped to handle interval-valued uncertainty than state-of-the-art.

Stability Training and Measurement System for Sportsperson (P84)

Balance and stability are very important for everybody and especially for sports-person who undergo extreme physical activities. Balance and stability exercises not only have a great impact on the performance of the sportsperson but also play a pivotal role in their rehabilitation. Therefore, it is very essential to have knowledge about a sportsperson’s balance and also to quantify the same. In this work, we propose a system consisting of a wobble board, with a gyro enhanced orientation sensor and a motion display for visual feedback to help the sportsperson improve their stability. The display unit gives in real time the orientation of the wobble board, which can help the sportsperson to apply necessary corrective forces to maintain neutral position. The system is compact and portable. We also quantify balance and stability using power spectral density. The sportsperson is made stand on the wobble board and the angular orientation of the wobble board is recorded for each 0.1 second interval. The signal is analized using discrete Fourier transforms. The power of this signal is related to the stability of the subject. This procedure is used to measure the balance and stability of an elite cricket team. Representative results are shown below: Table 1 represents power comparison of two subjects and Table 2 represents power comparison of left leg and right leg of one subject. This procedure can also be used in clinical practice to monitor improvement in stability dysfunction of sportsperson with injuries or other related problems undergoing rehabilitation.

Leveraging coherent distributed space-time codes for noncoherent communication in relay networks via training

For point to point multiple input multiple output systems, Dayal-Brehler-Varanasi have proved that training codes achieve the same diversity order as that of the underlying coherent space time block code (STBC) if a simple minimum mean squared error estimate of the channel formed using the training part is employed for coherent detection of the underlying STBC. In this letter, a similar strategy involving a combination of training, channel estimation and detection in conjunction with existing coherent distributed STBCs is proposed for noncoherent communication in Amplify-and-Forward (AF) relay networks. Simulation results show that the proposed simple strategy outperforms distributed differential space-time coding for AF relay networks. Finally, the proposed strategy is extended to asynchronous relay networks using orthogonal frequency division multiplexing.

On the Cubicity of Interval Graphs

A k-cube (or ``a unit cube in k dimensions'') is defined as the Cartesian product R-1 x . . . x R-k where R-i (for 1 <= i <= k) is an interval of the form [a(i), a(i) + 1] on the real line. The k-cube representation of a graph G is a mapping of the vertices of G to k-cubes such that the k-cubes corresponding to two vertices in G have a non-empty intersection if and only if the vertices are adjacent. The cubicity of a graph G, denoted as cub(G), is defined as the minimum dimension k such that G has a k-cube representation. An interval graph is a graph that can be represented as the intersection of intervals on the real line - i. e., the vertices of an interval graph can be mapped to intervals on the real line such that two vertices are adjacent if and only if their corresponding intervals overlap. We show that for any interval graph G with maximum degree Delta, cub(G) <= inverted right perpendicular log(2) Delta inverted left perpendicular + 4. This upper bound is shown to be tight up to an additive constant of 4 by demonstrating interval graphs for which cubicity is equal to inverted right perpendicular log(2) Delta inverted left perpendicular.

Reverse Channel Training For Reciprocal Mimo Systems With Spatial Multiplexing

This paper investigates the problem of designing reverse channel training sequences for a TDD-MIMO spatial-multiplexing system. Assuming perfect channel state information at the receiver and spatial multiplexing at the transmitter with equal power allocation to them dominant modes of the estimated channel, the pilot is designed to ensure an stimate of the channel which improves the forward link capacity. Using perturbation techniques, a lower bound on the forward link capacity is derived with respect to which the training sequence is optimized. Thus, the reverse channel training sequence makes use of the channel knowledge at the receiver. The performance of orthogonal training sequence with MMSE estimation at the transmitter and the proposed training sequence are compared. Simulation results show a significant improvement in performance.

Finite field computation technique for exact solution of systems of linear equations and interval linear programming problems

An error-free computational approach is employed for finding the integer solution to a system of linear equations, using finite-field arithmetic. This approach is also extended to find the optimum solution for linear inequalities such as those arising in interval linear programming probloms.

Joint evaluation of multiple speech patterns for speech recognition and training

We are addressing the novel problem of jointly evaluating multiple speech patterns for automatic speech recognition and training. We propose solutions based on both the non-parametric dynamic time warping (DTW) algorithm, and the parametric hidden Markov model (HMM). We show that a hybrid approach is quite effective for the application of noisy speech recognition. We extend the concept to HMM training wherein some patterns may be noisy or distorted. Utilizing the concept of ``virtual pattern'' developed for joint evaluation, we propose selective iterative training of HMMs. Evaluating these algorithms for burst/transient noisy speech and isolated word recognition, significant improvement in recognition accuracy is obtained using the new algorithms over those which do not utilize the joint evaluation strategy.

Cluster based training for scaling non-linear support vector machines

Support Vector Machines(SVMs) are hyperplane classifiers defined in a kernel induced feature space. The data size dependent training time complexity of SVMs usually prohibits its use in applications involving more than a few thousands of data points. In this paper we propose a novel kernel based incremental data clustering approach and its use for scaling Non-linear Support Vector Machines to handle large data sets. The clustering method introduced can find cluster abstractions of the training data in a kernel induced feature space. These cluster abstractions are then used for selective sampling based training of Support Vector Machines to reduce the training time without compromising the generalization performance. Experiments done with real world datasets show that this approach gives good generalization performance at reasonable computational expense.

Optimal Weighted Antenna Selection For Imperfect Channel Knowledge From Training

Receive antenna selection (AS) reduces the hardware complexity of multi-antenna receivers by dynamically connecting an instantaneously best antenna element to the available radio frequency (RF) chain. Due to the hardware constraints, the channels at various antenna elements have to be sounded sequentially to obtain estimates that are required for selecting the ``best'' antenna and for coherently demodulating data. Consequently, the channel state information at different antennas is outdated by different amounts. We show that, for this reason, simply selecting the antenna with the highest estimated channel gain is not optimum. Rather, the channel estimates of different antennas should be weighted differently, depending on the training scheme. We derive closed-form expressions for the symbol error probability (SEP) of AS for MPSK and MQAM in time-varying Rayleigh fading channels for arbitrary selection weights, and validate them with simulations. We then derive an explicit formula for the optimal selection weights that minimize the SEP. We find that when selection weights are not used, the SEP need not improve as the number of antenna elements increases, which is in contrast to the ideal channel estimation case. However, the optimal selection weights remedy this situation and significantly improve performance.

A Training-Based Iterative Detection/Channel Estimation Scheme for Large Non-Orthogonal STBC MIMO Systems

In this paper, we propose a training-based channel estimation scheme for large non-orthogonal space-time block coded (STBC) MIMO systems.The proposed scheme employs a block transmission strategy where an N-t x N-t pilot matrix is sent (for training purposes) followed by several N-t x N-t square data STBC matrices, where Nt is the number of transmit antennas. At the receiver, we iterate between channel estimation (using an MMSE estimator) and detection (using a low-complexity likelihood ascent search (LAS) detector) till convergence or for a fixed number of iterations. Our simulation results show that excellent bit error rate and nearness-to-capacity performance are achieved by the proposed scheme at low complexities. The fact that we could show such good results for large STBCs (e.g., 16 x 16 STBC from cyclic division algebras) operating at spectral efficiencies in excess of 20 bps/Hz (even after accounting for the overheads meant for pilot-based channel estimation and turbo coding) establishes the effectiveness of the proposed scheme.

Optimal Receive Antenna Selection in Time-Varying Fading Channels with Practical Training Constraints

Hardware constraints, which motivate receive antenna selection, also require that various antenna elements at the receiver be sounded sequentially to obtain estimates required for selecting the `best' antenna and for coherently demodulating data thereafter. Consequently, the channel state information at different antennas is outdated by different amounts and corrupted by noise. We show that, for this reason, simply selecting the antenna with the highest estimated channel gain is not optimum. Rather, a preferable strategy is to linearly weight the channel estimates of different antennas differently, depending on the training scheme. We derive closed-form expressions for the symbol error probability (SEP) of AS for MPSK and MQAM in time-varying Rayleigh fading channels for arbitrary selection weights, and validate them with simulations. We then characterize explicitly the optimal selection weights that minimize the SEP. We also consider packet reception, in which multiple symbols of a packet are received by the same antenna. New suboptimal, but computationally efficient weighted selection schemes are proposed for reducing the packet error rate. The benefits of weighted selection are also demonstrated using a practical channel code used in third generation cellular systems. Our results show that optimal weighted selection yields a significant performance gain over conventional unweighted selection.

A Novel, Balanced, and Energy-Efficient Training Method for Receive Antenna Selection

In receive antenna selection (AS), only signals from a subset of the antennas are processed at any time by the limited number of radio frequency (RF) chains available at the receiver. Hence, the transmitter needs to send pilots multiple times to enable the receiver to estimate the channel state of all the antennas and select the best subset. Conventionally, the sensitivity of coherent reception to channel estimation errors has been tackled by boosting the energy allocated to all pilots to ensure accurate channel estimates for all antennas. Energy for pilots received by unselected antennas is mostly wasted, especially since the selection process is robust to estimation errors. In this paper, we propose a novel training method uniquely tailored for AS that transmits one extra pilot symbol that generates accurate channel estimates for the antenna subset that actually receives data. Consequently, the transmitter can selectively boost the energy allocated to the extra pilot. We derive closed-form expressions for the proposed scheme's symbol error probability for MPSK and MQAM, and optimize the energy allocated to pilot and data symbols. Through an insightful asymptotic analysis, we show that the optimal solution achieves full diversity and is better than the conventional method.

Cubicity of Interval Graphs and the Claw Number

Let G(V, E) be a simple, undirected graph where V is the set of vertices and E is the set of edges. A b-dimensional cube is a Cartesian product l(1) x l(2) x ... x l(b), where each l(i) is a closed interval of unit length on the real line. The cub/city of G, denoted by cub(G), is the minimum positive integer b such that the vertices in G can be mapped to axis parallel b-dimensional cubes in such a way that two vertices are adjacent in G if and only if their assigned cubes intersect. An interval graph is a graph that can be represented as the intersection of intervals on the real line-i.e. the vertices of an interval graph can be mapped to intervals on the real line such that two vertices are adjacent if and only if their corresponding intervals overlap. Suppose S(m) denotes a star graph on m+1 nodes. We define claw number psi(G) of the graph to be the largest positive integer m such that S(m) is an induced subgraph of G. It can be easily shown that the cubicity of any graph is at least log(2) psi(G)]. In this article, we show that for an interval graph G log(2) psi(G)-]<= cub(G)<=log(2) psi(G)]+2. It is not clear whether the upper bound of log(2) psi(G)]+2 is tight: till now we are unable to find any interval graph with cub(G)> (log(2)psi(G)]. We also show that for an interval graph G, cub(G) <= log(2) alpha], where alpha is the independence number of G. Therefore, in the special case of psi(G)=alpha, cub(G) is exactly log(2) alpha(2)]. The concept of cubicity can be generalized by considering boxes instead of cubes. A b-dimensional box is a Cartesian product l(1) x l(2) x ... x l(b), where each I is a closed interval on the real line. The boxicity of a graph, denoted box(G), is the minimum k such that G is the intersection graph of k-dimensional boxes. It is clear that box(G)<= cub(G). From the above result, it follows that for any graph G, cub(G) <= box(G)log(2) alpha]. (C) 2010 Wiley Periodicals, Inc. J Graph Theory 65: 323-333, 2010

Epoch extraction from linear prediction residual for identification of closed glottis interval

In voiced speech analysis epochal information is useful in accurate estimation of pitch periods and the frequency response of the vocal tract system. Ideally, linear prediction (LP) residual should give impulses at epochs. However, there are often ambiguities in the direct use of LP residual since samples of either polarity occur around epochs. Further, since the digital inverse filter does not compensate the phase response of the vocal tract system exactly, there is an uncertainty in the estimated epoch position. In this paper we present an interpretation of LP residual by considering the effect of the following factors: 1) the shape of glottal pulses, 2) inaccurate estimation of formants and bandwidths, 3) phase angles of formants at the instants of excitation, and 4) zeros in the vocal tract system. A method for the unambiguous identification of epochs from LP residual is then presented. The accuracy of the method is tested by comparing the results with the epochs obtained from the estimated glottal pulse shapes for several vowel segments. The method is used to identify the closed glottis interval for the estimation of the true frequency response of the vocal tract system.

Training-Symbol Embedded, High-Rate Complex Orthogonal Designs for Relay Networks

Distributed Space-Time Block Codes (DSTBCs) from Complex Orthogonal Designs (CODs) (both square and non-square CODs other than the Alamouti design) are known to lose their single-symbol ML decodable (SSD) property when used in two-hop wireless relay networks using the amplify and forward protocol. For such a network, a new class of high rate, training-symbol embedded (TSE) SSD DSTBCs are proposed from TSE-CODs. The constructed codes include the training symbols within the structure of the code which is shown to be the key point to obtain high rate along with the SSD property. TSE-CODs are shown to offer full-diversity for arbitrary complex constellations. Non-square TSE-CODs are shown to provide better rates (in symbols per channel use) compared to the known SSD DSTBCs for relay networks when the number of relays is less than 10. Importantly, the proposed DSTBCs do not contain zeros in their codewords and as a result, antennas of the relay nodes do not undergo a sequence of switch on and off transitions within every codeword use. Hence, the proposed DSTBCs eliminate the antenna switching problem.