A Square-Root-Free Matrix Decomposition Method for Energy-Efficient Least Squares Computation on Embedded Systems

Fengbo Ren, Chenxin Zhang, Liang Liu, Wenyao Xu, Viktor Öwall, Dejan Markovic

Research output: Contribution to journalArticlepeer-review

7 Citations (SciVal)

Abstract

QR decomposition (QRD) is used to solve least squares (LS) problems for a wide range of applications. However, traditional QR decomposition methods, such as Gram-Schmidt (GS), require high computational complexity and non-linear operations to achieve high throughput, limiting their usage on resource-limited platforms. To enable efficient LS computation on embedded systems for real-time applications, this paper presents an alternative decomposition method, called QDRD, which relaxes system requirements while maintaining the same level of performance. Specifically, QDRD eliminates both the square-root operations in the normalization step and the divisions in the subsequent backward substitution. Simulation results show that the accuracy and reliability of factorization matrices can be significantly improved by QDRD, especially when executed on precision-limited platforms. Furthermore, benchmarking results on an embedded platform show that QDRD provides constantly better energy-efficiency and higher throughput than GS-QRD in solving LS problems. Up to 4 and 6.5 times improvement in energy-efficiency and throughput respectively can be achieved for small-size problems.
Original languageEnglish
Pages (from-to)73-76
JournalIEEE Embedded Systems Letters
Volume6
Issue number4
DOIs
Publication statusPublished - 2014

Subject classification (UKÄ)

  • Electrical Engineering, Electronic Engineering, Information Engineering

Keywords

  • QR decomposition
  • least squares problem
  • matrix factorization
  • computational complexity
  • energy efficiency

Fingerprint

Dive into the research topics of 'A Square-Root-Free Matrix Decomposition Method for Energy-Efficient Least Squares Computation on Embedded Systems'. Together they form a unique fingerprint.

Cite this