Information Recovery From Pairwise Measurements

Cited 6 time in webofscience Cited 0 time in scopus
  • Hit : 175
  • Download : 0
This paper is concerned with jointly recovering n node variables {x(i)}(1 <= i <= n) from a collection of pairwise difference measurements. Imagine we acquire a few observations taking the form of x(i) - x(j); the observation pattern is represented by a measurement graph G with an edge set E, such that x(i) - x(j) is observed if and only if (i, j) is an element of E. To account for noisy measurements in a general manner, we model the data acquisition process by a set of channels with given input/output transition measures. Employing information-theoretic tools applied to channel decoding problems, we develop a unified framework to characterize the fundamental recovery criterion, which accommodates general graph structures, alphabet sizes, and channel transition measures. In particular, our results isolate a family of minimum channel divergence measures to characterize the degree of measurement corruption, which together with the size of the minimum cut of G dictates the feasibility of exact information recovery. For various homogeneous graphs, the recovery condition depends almost only on the edge sparsity of the measurement graph irrespective of other graphical metrics; alternatively, the minimum sample complexity required for these graphs scales like (n log n)/(Hel(1/2)(min)) for certain information metric Hel(1/2)(min) defined in the main text, as long as the alphabet size is not super-polynomial in n. We apply our general theory to three concrete applications, including the stochastic block model, the random corruption model, and the haplotype assembly problem. Our theory leads to orderwise tight recovery conditions for all these scenarios
Publisher
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
Issue Date
2016-10
Language
English
Article Type
Article
Citation

IEEE TRANSACTIONS ON INFORMATION THEORY, v.62, no.10, pp.5881 - 5905

ISSN
0018-9448
DOI
10.1109/TIT.2016.2600566
URI
http://hdl.handle.net/10203/213850
Appears in Collection
EE-Journal Papers(저널논문)
Files in This Item
There are no files associated with this item.
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡ Click to see webofscience_button
⊙ Cited 6 items in WoS Click to see citing articles in records_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0