In this thesis we cover the mathematical foundations of the theory of compressive sensing. The problem in focus is the reconstruction of the vector \(\vec{x} \in \mathbb{C}^N\) from the measurement vector \(\vec{y} = \vec{Ax}\), where \(\vec{A} \in \mathbb{C}^{m \times N}\). Given that \(N = m\), it is enough to solve a square system of linear equations. If \(m < N\), the classical theory of linear algebra tells us that such systems can have a infinite number of solutions. However, if we assume that the vector \(\vec x\) is sparse, we are able to show that the reconstruction is not only possible, but efficient reconstruction algorithms exist. First chapter gives an introduction to the theory of sparse vectors. We define the notion of sparsity, derive the \(\ell_p\) bound for the best \(s\)-term sparse approximation of a vector \(\vec x\) and give two ways of defining compressible vectors. Which is of practical use because compressible vectors are much more common than perfectly sparse vectors in real world applications. Next, we investigate the minimal number \(m\) of measurements necessary for a perfect reconstruction and we see how the \(\ell_0\)-minimization \((P_0)\) naturally arises as a reconstruction strategy. Unfortunately, \(\ell_0\)-minimization is non-convex and additionally a NP-hard problem. We show this fact by reducing the well known NPhard problem of covering by 3-sets to the problem of \((P_0)\)-minimization. In the second chapter we give a summary of efficient reconstruction algorithms, which can be divided into three categories: optimization methods, greedy methods and threshold-based methods. In the optimization methods category the most important is the basis pursuit algorithm or \(\ell_1\)-minimization. We can think of it as a convex relaxation of the \((P_0)\) problem. Furthermore, we give a description of the OMP and CoSaMP greedy algorithms, and BT, IHT, HTP thresholding-based methods. The third chapter is dedicated to the \(\ell_1\)-minimization. We study the null-space property of the matrix \(\vec A\) and show how it ensures a successful reconstruction via the \(\vec x\) \(\ell_1\)-minimization. We introduce the definition of stability and robustness of a reconstruction method and prove how with a stronger version of the null-space property, \(\ell_1\)-minimization is both stable and robust. In chapter number four, we give the definition of coherence, which can be thought of as a reconstruction matrix \(\vec A\) quality. We derive some bounds and give an explicit construction of matrices with small coherence. Next, we analyse the conditions for coherence under which the reconstruction algorithms give a successful reconstruction. In the fifth chapter we introduce the notion of restricted isometry property, which is in fact a new quality measure for the matrix \(\vec A\), and this enables us to study the reconstruction algorithms for large values of sparsity \(s\). Same as with the coherence, we analyse the reconstruction algorithms with regard to the restricted isometry property. We should note that this thesis is not covering the whole theory of compressive sensing as it turns out that the explicit construction of matrices with a small restricted isometry constant is a hard problem which still hasn’t been resolved. A big step forward has been made by Terence Tao and Emmanuel Candes in [2], where they have shown that random Gauss matrices satisfy the restricted isometry property with a high probability and introduced stohastics into the theory of compressive sensing.