Top

Journal of Combinatorial Optimization

Published in:

22-10-2017

A low complexity semidefinite relaxation for large-scale MIMO detection

Authors: Rupaj Kumar Nayak, Mahendra Prasad Biswal

Published in: Journal of Combinatorial Optimization | Issue 2/2018

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Many wireless communication problems is based on a convex relaxation of the maximum likelihood problem which further can be cast as binary quadratic programs (BQPs). The two standard relaxation methods that are widely used for solving general BQPs such as spectral methods and semidefinite programming problem (SDP), each have their own advantages and disadvantages. It is widely accepted that small and medium sized SDP problems can be solved efficiently by interior point methods. Albeit, semidefinite relaxation has a tighter bound for large scale problems, but its computational complexity is high. However, Row-by-Row method (RBR) for solving SDPs could be opted for an alternative for large-scale MIMO detection because of low complexity. The present work is a spectral SDP-cut formulation to which the RBR is applied for large-scale MIMO detection. A modified RBR algorithm with tighter bound is presented to specify the efficiency in detecting massive MIMO.

previous article Properly colored trails, paths, and bridges

next article An approximation algorithm for soft capacitated k-facility location problem

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Available only for authorised users

Boyd S, Vandenberghe L (2004) Convex optimization. Cambridge University Press, CambridgeCrossRefMATH

Damen MO, Gamal HE, Caire G (2003) On maximum likelihood detection and the search for the closest lattice point. IEEE Trans Inf Theory 49:2389–2402MathSciNetCrossRefMATH

Foschini GJ (1996) Layered space-time architecture for wireless communication in a fading environment when using multi-element antennas. Bell Labs Tech J 1:41–59CrossRef

Grant M, Boyd S (2008) Graph implementations for nonsmooth convex programs. In: Blondel V, Boyd S, Kimura H (eds) Recent advances in learning and control (a tribute to M. Vidyasagar). Lecture notes in control and information sciences, Springer, pp 95–110

Grant M, Boyd S (2012) CVX Research, Inc. CVX: Matlab software for disciplined convex programming, version 2.0 beta

Jaldén J, Ottersten B (2005) On the complexity of sphere decoding in digital communications. IEEE Trans Signal Process 53:1474–1484MathSciNetCrossRefMATH

Kisialiou M, Luo X, Luo Z-Q (2009) Efficient implementation of quasimaximum likelihood detection based on semidefinite relaxation. IEEE Trans Signal Process 57:4811–4822MathSciNetCrossRef

Luo Z-Q, Chang T-H (2010) SDP relaxation of homogeneous quadratic optimization: approximation bounds and applications. In: Palomar DP, Eldar YC (eds) Convex optimization in signal processing and communications, chapter 4. Cambridge University Press, Cambridge

Luo Z-Q, Ma W-K, So AM-C, Ye Y et al (2010) Semidefinite relaxation of quadratic optimization problems. IEEE Signal Process Mag 27(3):20–34CrossRef

Ma W-K, Davidson TN, Wong KM et al (2002) Quasi-maximum-likelihood multiuser detection using semidefinite relaxation with application to synchronous CDMA. IEEE Trans Signal Process 50:912–922MathSciNetCrossRefMATH

Ma W-K, Ching PC, Ding Z (2004) Semidefinite relaxation based multiuser detection for M-ary PSK multiuser systems. IEEE Trans Signal Process 52:2862–2872CrossRef

Ma W-K, Su C-C, Jaldén J et al (2009) The equivalence of semidefinite relaxation MIMO detectors for higher order QAM. IEEE J Sel Top Signal Process 3:1038–1052CrossRef

Malick J (2007) Other manifestations of the Schur complement. Linear Algebra Appl 39:609–622MathSciNetMATH

Mobasher A, Taherzadeh M, Sotirov R et al (2007) A near-maximum-likelihood decoding algorithm for MIMO systems based on semidefinite programming. IEEE Trans Inf Theory 53:3869–3886CrossRefMATH

Steingrimsson B, Luo Z-Q, Wong KM (2003) Soft quasi-maximumlikelihood detection for multiple-antenna wireless channels. IEEE Trans Signal Process 51:2710–2719CrossRef

Sturm JF (1999) Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones. Optim Methods Softw 11:625–653MathSciNetCrossRefMATH

Tan P, Rasmussen L (2001) The application of semidefinite programming for detection in CDMA. IEEE J Sel Areas Commun 19:1442–1449CrossRef

Tarokh V, Seshadri N, Calderbank V (1998) Space-time codes for high data rate wireless communications: performance criterion and code construction. IEEE Trans Inf Theory 44:744–765MathSciNetCrossRefMATH

Toh KC, Todd MJ, Tütüncü RH (1999) SDPT3-a Matlab software package for semidefinite programming. Optim Methods Softw 11/12:545–581MathSciNetCrossRefMATH

Verdú S (1989) Computational complexity of optimum multiuser detection. Algorithmica 4:303–312MathSciNetCrossRefMATH

Wai H-T, Ma W-K, So A-MC (2011) Cheap semidefinite relaxation MIMO detection using Row-by-Row block coordinate descent. In: IEEE international conference on acoustics, speech and signal processing (ICASSP), pp 3256–3259

Wang P, Shen C, van den Hengel A (2013) A fast semidefinite approach to solving binary quadratic problems. In: Proceedings of IEEE conference on computer vision and pattern recognition

Wen Z, Goldfarb D, Ma S, Scheinberg K (2009) Row by row methods for semidefinite programming. Technical report, Department of IEOR, Columbia University

Zhang F (ed) (2005) The Schur complement and its applications Numerical methods and algorithms. Springer, Berlin, p 4

Title: A low complexity semidefinite relaxation for large-scale MIMO detection
Authors: Rupaj Kumar Nayak
Mahendra Prasad Biswal
Publication date: 22-10-2017
Publisher: Springer US
Published in: Journal of Combinatorial Optimization / Issue 2/2018
Print ISSN: 1382-6905
Electronic ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-017-0186-1

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 2/2018

On computing a minimum secure dominating set in block graphs

Bin packing game with a price of anarchy of

A certifying algorithm for lattice point feasibility in a system of UTVPI constraints

Vertex arboricity of planar graphs without intersecting 5-cycles

On vertex-parity edge-colorings

Upper bounds for adjacent vertex-distinguishing edge coloring

Premium Partner