MARC보기
LDR00000nam u2200205 4500
001000000433375
00520200225140853
008200131s2019 ||||||||||||||||| ||eng d
020 ▼a 9781085622547
035 ▼a (MiAaPQ)AAI13864424
040 ▼a MiAaPQ ▼c MiAaPQ ▼d 247004
0820 ▼a 629.8
1001 ▼a Chiu, Sung-En.
24510 ▼a Noisy Binary Search: Practical Algorithms and Applications.
260 ▼a [S.l.]: ▼b University of California, San Diego., ▼c 2019.
260 1 ▼a Ann Arbor: ▼b ProQuest Dissertations & Theses, ▼c 2019.
300 ▼a 114 p.
500 ▼a Source: Dissertations Abstracts International, Volume: 81-03, Section: A.
500 ▼a Advisor: Javidi, Tara.
5021 ▼a Thesis (Ph.D.)--University of California, San Diego, 2019.
506 ▼a This item must not be sold to any third party vendors.
520 ▼a This dissertation addresses the problem of searching a target within a region by sequential queries with noisy responses. A Bayesian decision maker is responsible to collect observation samples so as to enhance his knowledge about the true location in a speedy manner. When the response is noiseless, the classical binary search solves such a problem optimally. Noisy binary search, on the other hand, has also been formulated and studied extensively in theory over the past 60 years since Horstein (1963). However, the algorithms developed in noisy binary search problem find limited practical applications in real-world engineer problem. Motivated by bridging theory and practice, we formulate the noisy binary search problem by identifying practical scenarios and constraints that naturally rises with practical applications such as spectrum sensing in cognitive communication, AoA estimation by adaptive beamforming in large antenna array system, visual image inspection, bit-wise data transmission, heavy hitter detection in network system, etc.The first part of the dissertation (Chapter 2) focuses on theoretical understanding and developing noisy binary search algorithms under those practical constraints. Three algorithms sortPM, dyaPM, hiePM are proposed. Using the extrinsic Jensen Divergence from information theory, we provide upper bound for the expected search time of each of the algorithms. By comparing with an information theoretic lower bound, we demonstrate the asymptotic optimality and suboptimality of the proposed algorithms (asymptotic in the resolution of the target location).The second part of the dissertation applies the proposed hiePM to practical problems. In particular, Chapter 3 demonstrates the application of hiePM on the data transmission problem with noiseless feedback. The dyadic hierarchical query area of hiePM relates directly to the bit representation of the data stream. This simplifies significantly the corresponding adaptive encoding scheme and allows a bit-wise encoding. Chapter 4 considers the initial beam alignment problem in 5G mmWave communication using beamforming. With a single-path channel model, the problem is reduced to actively searching the Angle-of-Arrival (AoA) of the signal sent from the user to the Base Station (BS). hiePM is applied to adaptively and sequentially choose the beamforming from the hierarchical beamforming codebook. The proposed algorithm is compared to prior works of initial beam alignment that employs linear beam search, repeat binary search, or random beam search, respectively, and gives the state-of-art performance in terms of both AoA estimation error at the end of the initial alignment, and the spectral efficiency during the communication phase.
590 ▼a School code: 0033.
650 4 ▼a Electrical engineering.
650 4 ▼a Theoretical mathematics.
650 4 ▼a Information science.
650 4 ▼a Robotics.
690 ▼a 0544
690 ▼a 0642
690 ▼a 0723
690 ▼a 0771
71020 ▼a University of California, San Diego. ▼b Electrical and Computer Engineering.
7730 ▼t Dissertations Abstracts International ▼g 81-03A.
773 ▼t Dissertation Abstract International
790 ▼a 0033
791 ▼a Ph.D.
792 ▼a 2019
793 ▼a English
85640 ▼u http://www.riss.kr/pdu/ddodLink.do?id=T15491016 ▼n KERIS ▼z 이 자료의 원문은 한국교육학술정보원에서 제공합니다.
980 ▼a 202002 ▼f 2020
990 ▼a ***1816162
991 ▼a E-BOOK