Repository logo
  • English
  • 中文
Log In
Have you forgotten your password?
  1. Home
  2. College of Electrical Engineering and Computer Science / 電機資訊學院
  3. Electronics Engineering / 電子工程學研究所
  4. Warm-start Algorithm and Versatile Platform Design for Sparse Reconstruction Applications
 
  • Details

Warm-start Algorithm and Versatile Platform Design for Sparse Reconstruction Applications

Date Issued
2012
Date
2012
Author(s)
Yang, Tien-Ju
URI
http://ntur.lib.ntu.edu.tw//handle/246246/256685
Abstract
Sparsity is a property of the natural world. For decades, the sparsity of natural signals has played an important role in various fields such as data compression. The powerfulness of sparsity is also demonstrated in the human brains. In recent years, compressed sensing and sparse representation have attracted substantial attention in the signal processing and computer vision communities. Compressed sensing demonstrates that a sparse signal can be recovered precisely using a sampling rate lower than that proposed in Nyquist-Shannon theory; additionally, the compression is conducted as the signal is sensed. Sparse representation models a signal as a sparse linear combination of atoms from a dictionary, achieving state-of-the-art performance for several computer vision routines. These two techniques are built on sparse reconstruction algorithms. Sparse reconstruction algorithms solve an underdetermined system of linear equations based on the assumption that the answer or the target signal is sparse. The main challenge of sparse reconstruction is the high computational complexity, which hinders its integration into applications that require real-time processing or that have stringent power constraints. In this thesis, to address the issues mentioned previously, we propose a warm-start homotopy-based algorithm (WarmL1) and a corresponding platform for sparse signal reconstruction. WarmL1 provides a general method for rapidly reconstructing a sparse signal under several dynamic system modifications. Although the system is altered slightly, resolving the new problem from a base level requires significant computational resources. WarmL1 solves the new problem by adopting the previous result as the starting point rather than recalculating a new solution from the base level. According to the experimental results, the non-warm-start homotopy-based algorithm provides the most balanced performance regarding the need for measurements, speed, and reconstruction accuracy with noiseless and noisy measurements among existent non-warm-start algorithms. In this study, we also included several algorithm optimization methods for practical implementation. Extensive numerical experiments and applications were performed and proposed. The results show that WarmL1 can achieve 3.2x to 37.5x acceleration or up to 1/5100 l2-error at the same computational costs compared to that achieved in related works. The platform with the Application-Specific Integrated Circuit (ASIC) implementation enables real-time and low-power sparse reconstruction applications to be realized. Considering the versatility, the platform supports both compressed sensing and sparse representation applications, and both non-warm-start and warm-start reconstructions. The primary challenges are the high bandwidth demands, storage requirements, and computational complexity. To address the bandwidth and storage requirements, we proposed an online matrix generation scheme with fast state-skipping technique. In this scheme, only the seeds are stored, and the entries in the sensing matrix are randomly generated using the seeds and given state transitions. Thus, the storage requirements are reduced from 1 Gb to 10 Kb. Moreover, the fast state-skipping technique enables rapid random access to the sensing matrix. To address the high computational complexity, we proposed a multi-core design with 19 cores to provide a parallelism of up to 256. Additionally, each core can be disabled to reduce the power further. We also proposed a specifically designed randomly positioned stripe-based matrix to boost the speed further. Subsequently, we developed an efficient Cholesky-factorization-based linear algebra engine. A carefully designed data flow, efficient buffering mechanism, and in-place matrix updating technique were proposed. The proposed sparse reconstruction platform achieved 128.7 fps for the vehicle tracking application and 28.1 fps for the surveillance video reconstruction task, with a power of 242.4 mW. Thus, the real-time, low-power, and versatility requirements were satisfied.
Subjects
Sparse reconstruction
Warm start
Compressed sensing
Sparse representation
Multi-core design
Type
thesis
File(s)
Loading...
Thumbnail Image
Name

ntu-101-R99943034-1.pdf

Size

23.32 KB

Format

Adobe PDF

Checksum

(MD5):844c35ba2c2c1185aa8354123b91ddeb

臺大位居世界頂尖大學之列,為永久珍藏及向國際展現本校豐碩的研究成果及學術能量,圖書館整合機構典藏(NTUR)與學術庫(AH)不同功能平台,成為臺大學術典藏NTU scholars。期能整合研究能量、促進交流合作、保存學術產出、推廣研究成果。

To permanently archive and promote researcher profiles and scholarly works, Library integrates the services of “NTU Repository” with “Academic Hub” to form NTU Scholars.

總館學科館員 (Main Library)
醫學圖書館學科館員 (Medical Library)
社會科學院辜振甫紀念圖書館學科館員 (Social Sciences Library)

開放取用是從使用者角度提升資訊取用性的社會運動,應用在學術研究上是透過將研究著作公開供使用者自由取閱,以促進學術傳播及因應期刊訂購費用逐年攀升。同時可加速研究發展、提升研究影響力,NTU Scholars即為本校的開放取用典藏(OA Archive)平台。(點選深入了解OA)

  • 請確認所上傳的全文是原創的內容,若該文件包含部分內容的版權非匯入者所有,或由第三方贊助與合作完成,請確認該版權所有者及第三方同意提供此授權。
    Please represent that the submission is your original work, and that you have the right to grant the rights to upload.
  • 若欲上傳已出版的全文電子檔,可使用Open policy finder網站查詢,以確認出版單位之版權政策。
    Please use Open policy finder to find a summary of permissions that are normally given as part of each publisher's copyright transfer agreement.
  • 網站簡介 (Quickstart Guide)
  • 使用手冊 (Instruction Manual)
  • 線上預約服務 (Booking Service)
  • 方案一:臺灣大學計算機中心帳號登入
    (With C&INC Email Account)
  • 方案二:ORCID帳號登入 (With ORCID)
  • 方案一:定期更新ORCID者,以ID匯入 (Search for identifier (ORCID))
  • 方案二:自行建檔 (Default mode Submission)
  • 方案三:學科館員協助匯入 (Email worklist to subject librarians)

Built with DSpace-CRIS software - Extension maintained and optimized by 4Science