کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
430960 688238 2012 17 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Strengthening hash families and compressive sensing
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Strengthening hash families and compressive sensing
چکیده انگلیسی

The deterministic construction of measurement matrices for compressive sensing is a challenging problem, for which a number of combinatorial techniques have been developed. One of them employs a widely used column replacement technique based on hash families. It is effective at producing larger measurement matrices from smaller ones, but it can only preserve the strength (level of sparsity supported), not increase it. Column replacement is extended here to produce measurement matrices with larger strength from ingredient arrays with smaller strength. To do this, a new type of hash family, called a strengthening hash family, is introduced. Using these hash families, column replacement is shown to increase strength under two standard notions of recoverability. Then techniques to construct strengthening hash families, both probabilistically and deterministically, are developed. Using a variant of the Stein–Lovász–Johnson theorem, a deterministic, polynomial time algorithm for constructing a strengthening hash family of fixed strength is derived.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 16, October 2012, Pages 170–186
نویسندگان
, , ,