Compressed sensing is a framework in signal processing that enables the efficient acquisition and reconstruction of sparse signals. A widely-used class of algorithms that are used for this reconstruction, called greedy-algorithms, depend on non-convex optimization. With increasing signal size, these problems become computationally very hard. Block compressed sensing is a framework in compressed sensing that divides the compressed sensing problem into sub-problems, gaining a better storage complexity. However, block compressed sensing has not yet been studied form a computational complexity perspective.

This thesis focuses on the application of block compressed sensing to signals of high dimension to gain insight into the relation between reconstruction performance and computational complexity. This is done by, first investigating how theoretical reconstruction guarantees change, when the problem is divided into smaller sub-problems and by doing a complexity analysis of the reconstruction itself. Each sub-problem solves for a portion of a signal, defined as a block. Next, experiments are conducted in order to get insight into the trade-off between computational complexity and quality of the reconstruction. It can be found that, by using this block-wise approach, the computational complexity of the reconstruction problem decreases, but at the same time, quality of the reconstruction deteriorates. Besides, a method to compensate for this performance loss is proposed. The key idea of this method is that, by propagating prior information among the different blocks, the reconstructions of the blocks can be improved. Finally, block compressed sensing and prior-aware block compressed sensing are analysed in a higher order tensor compressed sensing setting. Nevertheless, this setting was found to exhibit a less favourable complexity-performance trade-off than the normal one, as this setting resulted in both a more complex and a less accurate reconstruction than the normal one.