Feedback Overhead-Aware, Distributed, Fast, and Reliable Selection

In a communication system in which K nodes communicate with a central sink node, the following problem of selection often occurs. Each node maintains a preference number called a metric, which is not known to other nodes. The sink node must find the `best' node with the largest metric. The local nature of the metrics requires the selection process to be distributed. Further, the selection needs to be fast in order to increase the fraction of time available for data transmission using the selected node and to handle time-varying environments. While several selection schemes have been proposed in the literature, each has its own shortcomings. We propose a novel, distributed selection scheme that generalizes the best features of the timer scheme, which requires minimal feedback but does not guarantee successful selection, and the splitting scheme, which requires more feedback but guarantees successful selection. The proposed scheme introduces several new ideas into the design of the timer and splitting schemes. It explicitly accounts for feedback overheads and guarantees selection of the best node. We analyze and optimize the performance of the scheme and show that it is scalable, reliable, and fast. We also present new insights about the optimal timer scheme.

Turning visual search time on its head

Our everyday visual experience frequently involves searching for objects in clutter. Why are some searches easy and others hard? It is generally believed that the time taken to find a target increases as it becomes similar to its surrounding distractors. Here, I show that while this is qualitatively true, the exact relationship is in fact not linear. In a simple search experiment, when subjects searched for a bar differing in orientation from its distractors, search time was inversely proportional to the angular difference in orientation. Thus, rather than taking search reaction time (RT) to be a measure of target-distractor similarity, we can literally turn search time on its head (i.e. take its reciprocal 1/RT) to obtain a measure of search dissimilarity that varies linearly over a large range of target-distractor differences. I show that this dissimilarity measure has the properties of a distance metric, and report two interesting insights come from this measure: First, for a large number of searches, search asymmetries are relatively rare and when they do occur, differ by a fixed distance. Second, search distances can be used to elucidate object representations that underlie search - for example, these representations are roughly invariant to three-dimensional view. Finally, search distance has a straightforward interpretation in the context of accumulator models of search, where it is proportional to the discriminative signal that is integrated to produce a response. This is consistent with recent studies that have linked this distance to neuronal discriminability in visual cortex. Thus, while search time remains the more direct measure of visual search, its reciprocal also has the potential for interesting and novel insights. (C) 2012 Elsevier Ltd. All rights reserved.

Is saccade averaging determined by visual processing or movement planning?

Bhutani N, Ray S, Murthy A. Is saccade averaging determined by visual processing or movement planning? J Neurophysiol 108: 3161-3171, 2012. First published September 26, 2012; doi:10.1152/jn.00344.2012.-Saccadic averaging that causes subjects' gaze to land between the location of two targets when faced with simultaneously or sequentially presented stimuli has been often used as a probe to investigate the nature of computations that transform sensory representations into an oculomotor plan. Since saccadic movements involve at least two processing stages-a visual stage that selects a target and a movement stage that prepares the response-saccade averaging can either occur due to interference in visual processing or movement planning. By having human subjects perform two versions of a saccadic double-step task, in which the stimuli remained the same, but different instructions were provided (REDIRECT gaze to the later-appearing target vs. FOLLOW the sequence of targets in their order of appearance), we tested two alternative hypotheses. If saccade averaging were due to visual processing alone, the pattern of saccade averaging is expected to remain the same across task conditions. However, whereas subjects produced averaged saccades between two targets in the FOLLOW condition, they produced hypometric saccades in the direction of the initial target in the REDIRECT condition, suggesting that the interaction between competing movement plans produces saccade averaging.

Active Sequential Hypothesis Testing with Application to a Visual Search Problem

We consider a visual search problem studied by Sripati and Olson where the objective is to identify an oddball image embedded among multiple distractor images as quickly as possible. We model this visual search task as an active sequential hypothesis testing problem (ASHT problem). Chernoff in 1959 proposed a policy in which the expected delay to decision is asymptotically optimal. The asymptotics is under vanishing error probabilities. We first prove a stronger property on the moments of the delay until a decision, under the same asymptotics. Applying the result to the visual search problem, we then propose a ``neuronal metric'' on the measured neuronal responses that captures the discriminability between images. From empirical study we obtain a remarkable correlation (r = 0.90) between the proposed neuronal metric and speed of discrimination between the images. Although this correlation is lower than with the L-1 metric used by Sripati and Olson, this metric has the advantage of being firmly grounded in formal decision theory.

Similarity relations in visual search predict rapid visual categorization

How do we perform rapid visual categorization?It is widely thought that categorization involves evaluating the similarity of an object to other category items, but the underlying features and similarity relations remain unknown. Here, we hypothesized that categorization performance is based on perceived similarity relations between items within and outside the category. To this end, we measured the categorization performance of human subjects on three diverse visual categories (animals, vehicles, and tools) and across three hierarchical levels (superordinate, basic, and subordinate levels among animals). For the same subjects, we measured their perceived pair-wise similarities between objects using a visual search task. Regardless of category and hierarchical level, we found that the time taken to categorize an object could be predicted using its similarity to members within and outside its category. We were able to account for several classic categorization phenomena, such as (a) the longer times required to reject category membership; (b) the longer times to categorize atypical objects; and (c) differences in performance across tasks and across hierarchical levels. These categorization times were also accounted for by a model that extracts coarse structure from an image. The striking agreement observed between categorization and visual search suggests that these two disparate tasks depend on a shared coarse object representation.

Feedback overhead-aware fast distributed selection scheme for multi-node wireless systems

Opportunistic selection is a practically appealing technique that is used in multi-node wireless systems to maximize throughput, implement proportional fairness, etc. However, selection is challenging since the information about a node's channel gains is often available only locally at each node and not centrally. We propose a novel multiple access-based distributed selection scheme that generalizes the best features of the timer scheme, which requires minimal feedback but does not always guarantee successful selection, and the fast splitting scheme, which requires more feedback but guarantees successful selection. The proposed scheme's design explicitly accounts for feedback time overheads unlike the conventional splitting scheme and guarantees selection of the user with the highest metric unlike the timer scheme. We analyze and minimize the average time including feedback required by the scheme to select. With feedback overheads, the proposed scheme is scalable and considerably faster than several schemes proposed in the literature. Furthermore, the gains increase as the feedback overhead increases.

Optimal MSE solution for a decision feedback equalizer

Due to the inherent feedback in a decision feedback equalizer (DFE) the minimum mean square error (MMSE) or Wiener solution is not known exactly. The main difficulty in such analysis is due to the propagation of the decision errors, which occur because of the feedback. Thus in literature, these errors are neglected while designing and/or analyzing the DFEs. Then a closed form expression is obtained for Wiener solution and we refer this as ideal DFE (IDFE). DFE has also been designed using an iterative and computationally efficient alternative called least mean square (LMS) algorithm. However, again due to the feedback involved, the analysis of an LMS-DFE is not known so far. In this paper we theoretically analyze a DFE taking into account the decision errors. We study its performance at steady state. We then study an LMS-DFE and show the proximity of LMS-DFE attractors to that of the optimal DFE Wiener filter (obtained after considering the decision errors) at high signal to noise ratios (SNR). Further, via simulations we demonstrate that, even at moderate SNRs, an LMS-DFE is close to the MSE optimal DFE. Finally, we compare the LMS DFE attractors with IDFE via simulations. We show that an LMS equalizer outperforms the IDFE. In fact, the performance improvement is very significant even at high SNRs (up to 33%), where an IDFE is believed to be closer to the optimal one. Towards the end, we briefly discuss the tracking properties of the LMS-DFE.

Mapping joint ROM on a cube using electromagnetic trackers

This paper presents a unified framework using the unit cube for measurement, representation and usage of the range of motion (ROM) of body joints with multiple degrees of freedom (d.o.f) to be used for digital human models (DHM). Traditional goniometry needs skill and kn owledge; it is intrusive and has limited applicability for multi-d.o.f. joints. Measurements using motion capture systems often involve complicated mathematics which itself need validation. In this paper we use change of orientation as the measure of rotation; this definition does not require the identification of any fixed axis of rotation. A two-d.o.f. joint ROM can be represented as a Gaussian map. Spherical polygon representation of ROM, though popular, remains inaccurate, vulnerable due to singularities on parametric sphere and difficult to use for point classification. The unit cube representation overcomes these difficulties. In the work presented here, electromagnetic trackers have been effectively used for measuring the relative orientation of a body segment of interest with respect to another body segment. The orientation is then mapped on a surface gridded cube. As the body segment is moved, the grid cells visited are identified and visualized. Using the visual display as a feedback, the subject is instructed to cover as many grid cells as he can. In this way we get a connected patch of contiguous grid cells. The boundary of this patch represents the active ROM of the concerned joint. The tracker data is converted into the motion of a direction aligned with the axis of the segment and a rotation about this axis later on. The direction identifies the grid cells on the cube and rotation about the axis is represented as a range and visualized using color codes. Thus the present methodology provides a simple, intuitive and accura te determination and representation of up to 3 d.o.f. joints. Basic results are presented for the shoulder. The measurement scheme to be used for wrist and neck, and approach for estimation of the statistical distribution of ROM for a given population are also discussed.

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.

Joint evaluation of channel feedback schemes, rate adaptation, and scheduling in OFDMA downlinks with feedback delays

Orthogonal frequency-division multiple access (OFDMA) systems divide the available bandwidth into orthogonal subchannels and exploit multiuser diversity and frequency selectivity to achieve high spectral efficiencies. However, they require a significant amount of channel state feedback for scheduling and rate adaptation and are sensitive to feedback delays. We develop a comprehensive analysis for OFDMA system throughput in the presence of feedback delays as a function of the feedback scheme, frequency-domain scheduler, and rate adaptation rule. Also derived are expressions for the outage probability, which captures the inability of a subchannel to successfully carry data due to the feedback scheme or feedback delays. Our model encompasses the popular best-n and threshold-based feedback schemes and the greedy, proportional fair, and round-robin schedulers that cover a wide range of throughput versus fairness tradeoff. It helps quantify the different robustness of the schedulers to feedback overhead and delays. Even at low vehicular speeds, it shows that small feedback delays markedly degrade the throughput and increase the outage probability. Further, given the feedback delay, the throughput degradation depends primarily on the feedback overhead and not on the feedback scheme itself. We also show how to optimize the rate adaptation thresholds as a function of feedback delay.

Enhancing reproducibility of ultrasonic measurements by new users

Perception of operator influences ultrasound image acquisition and processing. Lower costs are attracting new users to medical ultrasound. Anticipating an increase in this trend, we conducted a study to quantify the variability in ultrasonic measurements made by novice users and identify methods to reduce it. We designed a protocol with four presets and trained four new users to scan and manually measure the head circumference of a fetal phantom with an ultrasound scanner. In the first phase, the users followed this protocol in seven distinct sessions. They then received feedback on the quality of the scans from an expert. In the second phase, two of the users repeated the entire protocol aided by visual cues provided to them during scanning. We performed off-line measurements on all the images using a fully automated algorithm capable of measuring the head circumference from fetal phantom images. The ground truth (198.1 +/- 1.6 mm) was based on sixteen scans and measurements made by an expert. Our analysis shows that: (1) the inter-observer variability of manual measurements was 5.5 mm, whereas the inter-observer variability of automated measurements was only 0.6 mm in the first phase (2) consistency of image appearance improved and mean manual measurements was 4-5 mm closer to the ground truth in the second phase (3) automated measurements were more precise, accurate and less sensitive to different presets compared to manual measurements in both phases. Our results show that visual aids and automation can bring more reproducibility to ultrasonic measurements made by new users.

Joint Evaluation of Reduced Feedback Scheme, Scheduling, and Rate Adaptation in OFDMA Systems with Feedback Delays

Orthogonal frequency division multiple access (OFDMA) systems exploit multiuser diversity and frequency-selectivity to achieve high spectral efficiencies. However, they require considerable feedback for scheduling and rate adaptation, and are sensitive to feedback delays. We develop a comprehensive analysis of the OFDMA system throughput as a function of the feedback scheme, frequency-domain scheduler, and discrete rate adaptation rule in the presence of feedback delays. We analyze the popular best-n and threshold-based feedback schemes. We show that for both the greedy and round-robin schedulers, the throughput degradation, given a feedback delay, depends primarily on the fraction of feedback reduced by the feedback scheme and not the feedback scheme itself. Even small feedback delays at low vehicular speeds are shown to significantly degrade the throughput. We also show that optimizing the link adaptation thresholds as a function of the feedback delay can effectively counteract the detrimental effect of delays.

An adaptive modulation scheme for two-user fading MAC with quantized fade state feedback

For transmission over the two-user Gaussian Multiple Access Channel with fading and finite constellation at the inputs, we propose a scheme which uses only quantized knowledge of fade state at users with the feedback overhead being nominal. One of the users rotates its constellation without varying the transmit power to adapt to the existing channel conditions, in order to meet certain pre-determined minimum Euclidean distance requirement in the equivalent constellation at the destination. The optimal modulation scheme has been described for the case when both the users use symmetric M-PSK constellations at the input, where M = 2λ, λ being a positive integer. The strategy has been illustrated by considering examples where both the users use QPSK signal set at the input. 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 [log2 (M2/8 - M/4 + 2)] + 1 bits, for the M-PSK case.

Does linear separability really matter? Complex visual search is explained by simple search

Visual search in real life involves complex displays with a target among multiple types of distracters, but in the laboratory, it is often tested using simple displays with identical distracters. Can complex search be understood in terms of simple searches? This link may not be straightforward if complex search has emergent properties. One such property is linear separability, whereby search is hard when a target cannot be separated from its distracters using a single linear boundary. However, evidence in favor of linear separability is based on testing stimulus configurations in an external parametric space that need not be related to their true perceptual representation. We therefore set out to assess whether linear separability influences complex search at all. Our null hypothesis was that complex search performance depends only on classical factors such as target-distracter similarity and distracter homogeneity, which we measured using simple searches. Across three experiments involving a variety of artificial and natural objects, differences between linearly separable and nonseparable searches were explained using target-distracter similarity and distracter heterogeneity. Further, simple searches accurately predicted complex search regardless of linear separability (r = 0.91). Our results show that complex search is explained by simple search, refuting the widely held belief that linear separability influences visual search.

Full-rate full-diversity finite feedback space-time schemes with minimum feedback and transmission duration

A Finite Feedback Scheme (FFS) for a quasi-static MIMO block fading channel with finite N-ary delay-free noise-free feedback consists of N Space-Time Block Codes (STBCs) at the transmitter, one corresponding to each possible value of feedback, and a function at the receiver that generates N-ary feedback. A number of FFSs are available in the literature that provably attain full-diversity. However, there is no known full-diversity criterion that universally applies to all FFSs. In this paper a universal necessary condition for any FFS to achieve full-diversity is given, and based on this criterion the notion of Feedback-Transmission duration optimal (FT-optimal) FFSs is introduced, which are schemes that use minimum amount of feedback N for the given transmission duration T, and minimum T for the given N to achieve full-diversity. When there is no feedback (N = 1) an FT-optimal scheme consists of a single STBC, and the proposed condition reduces to the well known necessary and sufficient condition for an STBC to achieve full-diversity. Also, a sufficient criterion for full-diversity is given for FFSs in which the component STBC yielding the largest minimum Euclidean distance is chosen, using which full-rate (N-t complex symbols per channel use) full-diversity FT-optimal schemes are constructed for all N-t > 1. These are the first full-rate full-diversity FFSs reported in the literature for T < N-t. Simulation results show that the new schemes have the best error performance among all known FFSs.