상세정보
Export to Refworks부가기능
Noisy Binary Search: Practical Algorithms and Applications
상세 프로파일
| 자료유형 | 학위논문 |
|---|---|
| 서명/저자사항 | Noisy Binary Search: Practical Algorithms and Applications. |
| 개인저자 | Chiu, Sung-En. |
| 단체저자명 | University of California, San Diego. Electrical and Computer Engineering. |
| 발행사항 | [S.l.]: University of California, San Diego., 2019. |
| 발행사항 | Ann Arbor: ProQuest Dissertations & Theses, 2019. |
| 형태사항 | 114 p. |
| 기본자료 저록 | Dissertations Abstracts International 81-03A. Dissertation Abstract International |
| ISBN | 9781085622547 |
| 학위논문주기 | Thesis (Ph.D.)--University of California, San Diego, 2019. |
| 일반주기 |
Source: Dissertations Abstracts International, Volume: 81-03, Section: A.
Advisor: Javidi, Tara. |
| 이용제한사항 | This item must not be sold to any third party vendors. |
| 요약 | 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. |
| 일반주제명 | Electrical engineering. Theoretical mathematics. Information science. Robotics. |
| 언어 | 영어 |
| 바로가기 | 
: 이 자료의 원문은 한국교육학술정보원에서 제공합니다. |
