Ma trận ngẫu nhiên
Ma trận ngẫu nhiên có 2 loại là ma trận ngẫu nhiên không có cấu trúc và
ma trận ngẫu nhiên có cấu trúc. Ma trận ngẫu nhiên không có cấu trúc với
các phần tử được tạo ra ngẫu nhiên theo một phân bố xác suất như Gauss và
Bernoulli [9]. Một ma trận ngẫu nhiên có kích thước N × N được tạo thành,
sau đó từ M hàng của ma trận ban đầu sẽ được chọn ngẫu nhiên để tạo thành
ma trận lấy mẫu nén. Các ma trận dạng này có ưu điểm dễ xây dựng và đáp
ứng tiêu chí RIP với xác suất cao. Tuy nhiên, chúng có một số hạn chế trong
thực tế bởi các phần tử trong ma trận là các số thực dấu phảy động nên không
khả thi với các bài toán quy mô lớn do khối lượng tính toán và cần bộ nhớ để
lưu trữ lớn.
Loại ma trận ngẫu nhiên có cấu trúc với các phần tử được tạo thành từ
một hàm hoặc một cấu trúc nhất định. Sau đó các hàng được lựa chọn ngẫu
nhiên từ các cấu trúc ban đầu để tạo ra ma trận lấy mẫu nén. Các ví dụ
điển hình của loại ma trận này là các ma trận con được tạo thành từ ma
trận Fourier [103] và ma trận Hadamard [86]. Các ma trận loại này có ưu
điểm làm tăng tốc trong quá trình khôi phục lại tín hiệu. Tuy nhiên, chúng
có nhược điểm là không ổn định, lỗi khôi phục cao và yêu cầu số hàng của ma
trận lấy mẫu lớn.
Ma trận xác định
Ma trận lấy mẫu xác định là ma trận được thiết kế theo các cấu trúc xác
định và đáp ứng tiêu chí RIP hoặc tính chất không kết hợp (incoherent). Một
số ma trận lấy mẫu xác định đã được đề xuất để giải quyết các vấn đề của
ma trận ngẫu nhiên [5], [59], [60], [107]. Ma trận xác định được phân thành
2 loại là ma trận bán xác định và ma trận xác định toàn phần.
Các ma trận bán xác định thường được tạo thành qua 2 bước. Bước thứ
nhất là tạo cột đầu tiên với các phần tử ngẫu nhiên và bước thứ hai là tạo ma
trận đầy đủ bằng cách áp dụng một phép biến đổi đơn giản trên cột đầu tiên,
chẳng hạn như phép quay để tạo ra từng hàng của ma trận. Ví dụ điển hình
về ma trận loại này là ma trận Circulant và Toeplitz [83]. Các ma trận dạng
này có ưu điểm dễ xây dựng, giảm tính ngẫu nhiên và sử dụng ít bộ nhớ hơn
so với ma trận ngẫu nhiên không có cấu trúc. Các ma trận này không thực
sự phổ biến và chỉ được áp dụng trong một số ứng dụng cụ thể.
Ma trận loại xác định toàn phần là ma trận có cấu trúc xác định hoàn toàn
nhằm thỏa mãn tiêu chí RIP hoặc tính chất không kết hợp. Các ví dụ điển
hình về loại ma trận có cấu trúc xác định toàn phần là ma trận cấu tạo từ
mã nhị phân tuần hoàn BCH [7] và ma trận cấu tạo từ mã không tuần hoàn
chirp [84]. Các ma trận xác định toàn phần có ưu điểm là thời gian thực hiện
nhanh, đơn giản trong quá trình lấy mẫu, giảm độ phức tạp tính toán. Tuy
nhiên, chúng có nhược điểm là kích thước ma trận không thể lựa chọn tùy ý,
khó khăn để xác định tiêu chí RIP.