Compressed sensing is a rapidly growing research field in signal and image processing, machine learning, statistics, and systems control. In this survey paper, we provide a review of the theoretical foundations of compressed sensing and present state-of-the-art algorithms for solving the corresponding optimization problems. Additionally, we discuss several practical applications of compressed sensing, such as group testing, sparse system identification, and sparse feedback gain design, and demonstrate their effectiveness through Python programs. This survey paper aims to contribute to the advancement of compressed sensing research and its practical applications in various scientific disciplines.

The aim of this paper is to show an upper bound for finding defective samples in a group testing framework. To this end, we exploit minimization of Hamming weights in coding theory and define probability of error for our decoding scheme. We derive a new upper bound on the probability of error. We show that both upper and lower bounds coincide with each other at an optimal density ratio of a group matrix. We conclude that as defective rate increases, a group matrix should be sparser to find defective samples with only a small number of tests.

In this paper, we consider a group testing (GT) problem. We derive a lower bound on the probability of error for successful decoding of defected binary signals. To this end, we exploit Fano's inequality theorem in the information theory. We show that the probability of error is bounded as an entropy function, a density of a pooling matrix and a sparsity of a binary signal. We evaluate that for decoding of highly sparse signals, the pooling matrix is required to be dense. Conversely, if dense signals are needed to decode, the sparse pooling matrix should be designed to achieve the small probability of error.

The main contribution of this paper is a non-trivial expression, that is called dual expression, of the posterior values for non-adaptive group testing problems. The dual expression is useful for exact bitwise MAP estimation. We assume a simplest non-adaptive group testing scenario including N-objects with binary status and M-tests. If a group contains one or more positive object, the test result for the group is assumed to be one; otherwise, the test result becomes zero. Our inference problem is to evaluate the posterior probabilities of the objects from the observation of M-test results and the prior probabilities for objects. The derivation of the dual expression of posterior values can be naturally described based on a holographic transformation to the normal factor graph (NFG) representing the inference problem. In order to handle OR constraints in the NFG, we introduce a novel holographic transformation that converts an OR function to a function similar to an EQUAL function.