Result: Lower Bound on Expected Complexity of Depth-First Tree Search with Multiple Radii

Title:
Lower Bound on Expected Complexity of Depth-First Tree Search with Multiple Radii
Authors:
AHN, Junil, KIM, Kiseon
Source:
IEEE communications letters. 16(6):805-808
Publisher Information:
New York, NY: Institute of Electrical and Electronics Engineers, 2012.
Publication Year:
2012
Physical Description:
print, 9 ref
Original Material:
INIST-CNRS
Subject Terms:
Telecommunications, Télécommunications, Sciences exactes et technologie, Exact sciences and technology, Sciences appliquees, Applied sciences, Telecommunications et theorie de l'information, Telecommunications and information theory, Télécommunications, Telecommunications, Systèmes, réseaux et services de télécommunications, Systems, networks and services of telecommunications, Transmission et modulation (techniques et équipements), Transmission and modulation (techniques and equipments), Algorithme en arbre, Tree algorithm, Algoritmo del árbol, Algorithme recherche, Search algorithm, Algoritmo búsqueda, Borne inférieure, Lower bound, Cota inferior, Borne supérieure, Upper bound, Cota superior, Complexité algorithme, Algorithm complexity, Complejidad algoritmo, Méthode analytique, Analytical method, Método analítico, Problème moindre carré, Least squares problem, Problema minimos cuadrados, Transformation Fourier discrète, Discrete Fourier transformation, Transformación Fourier discreta, Transmission information, Information transmission, Transmisión información, Transmission onde, Wave transmission, Transmisión onda, Algorithmic complexity, depth-first tree search algorithm, integer least-squares problem, lower bound analysis
Document Type:
Academic journal Article
File Description:
text
Language:
English
Author Affiliations:
School of Information and Mechatronics, Department of Nanobio Materials and Electronics, WCU, Gwangju Institute of Science and Technology (GIST), 1 Oryong-dong, Buk-gu, Gwangju 500-712, Korea, Republic of
ISSN:
1089-7798
Access URL:
http://pascal-francis.inist.fr/vibad/index.php?action=search&terms=26015922
Rights:
Copyright 2015 INIST-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Telecommunications and information theory
Accession Number:
edscal.26015922
Database:
PASCAL Archive

Further Information

Depth-first tree search with multiple radii (DFTS-MR) algorithm attains significant complexity reduction over DFTS with a single radius (DFTS-SR) for solving integer least-squares (ILS) problems. Herein, we derive the lower bound on the expected complexity of DFTS-MR under i.i.d. complex Gaussian environments. Currently, the upper bound on the expected DFTS-MR complexity is known. Our analytical result shows the computational dependence on the statistics of the channel, the noise, and the transmitted symbols. It also reflects the use of multiple radii, which is one of the main characteristics of DFTS-MR. The resultant lower bound provides an efficient means to better understand the complexity behavior of DFTS-MR, along with the (known) upper bound.