Nonconvex compressed sensing (which is the subject of this paper) deals with both the theoretical problem of determining whether a sparse signal (i.e., an $N$ $N$ -vector with $s\ll N$ $s\ll N$ nonzero components) can be reconstructed exactly from fewer measurements than those established by classical sampling theory, and the practical problem of eventually reconstructing it. In the noiseless case, the linear algebra involved amounts to finding the sparsest solution of an underdetermined linear system, but instead of minimizing the $\ell_1$ $\ell_1$ norm (i.e., a convex problem) of the solution as in basis pursuit, the nonconvex variant minimizes its $\ell_p$ $\ell_p$ quasi-norm with $0<p<1$ $0&lt;p&lt;1$ . Recovery in the presence of noise is also considered here, in which equality constraints are replaced by the $\ell_2$ $\ell_2$ norm of the residual required to be less than or equal to a given tolerance.
   Besides a correction of a previous result by R. Chartrand [IEEE Signal Process. Lett. 14 (2007), no. 10, 707--710] (admittedly included too in page 4 of [R. Chartrand and V. Staneva, Inverse Problems 24 (2008), no. 3, 035020, 14 pp.; MR2421974 (2009d:94027)]), the theoretical contributions of this paper are not established in terms of restricted isometry constants as usual. The authors use asymmetric (and hence sharper) bounds on the 2-norm condition number of all submatrices formed with at most $2s$ $2s$ columns of the matrix of the linear system; these bounds could be estimated by computing the singular values of a large number of randomly selected submatrices, and they allow the authors to slightly improve a classical condition by Candès when $p=1$ $p=1$ . A sufficient condition for the approximate recovery in the noisy case is also given.
   The practical contributions begin by describing an $\epsilon$ $\epsilon$ -regularized iteratively reweighted $\ell_1$ $\ell_1$ minimization algorithm, which turns out to be quite similar to that of [E. J. Candès, M. B. Wakin and S. P. Boyd, J. Fourier Anal. Appl. 14 (2008), no. 5-6, 877--905; MR2461611 (2010b:90088)] where $p=0$ $p=0$ . In both algorithms, the diagonal weight matrix is positive definite and the nonincreasing regularization sequence is allowed not to be constant. Although convergence is not proven, a detailed analysis is provided along with a small counterexample illustrating the necessary conditions for the starting vector. The paper concludes with some numerical experiments to show that $p=0$ $p=0$ is not always the best choice (with $p$ $p$ fixed) and demonstrating that the algorithm outperforms four existing algorithms when $p<1$ $p&lt;1$ is allowed to successively increase from 0 at run time.

By "spline function'' the authors mean a smooth (usually once or twice differentiable) piecewise polynomial function defined on a partition of a two- or three-dimensional domain, usually into triangles or tetrahedra.
   Univariate splines (smooth piecewise polynomial functions of one variable, defined on a partition of an interval) were developed mostly in the 1960s and '70s. They are used ubiquitously in a wide range of application areas and now form a standard topic in numerical analysis textbooks. The bulk of the work on multivariate splines started in the late '70s, reached its heyday in the '80s and '90s, and is ongoing. Multivariate splines have applications in areas such as scattered data interpolation, function approximation, geometric design, surface representation and processing, and the numerical solution of partial differential equations.
   The monograph under review here is the definitive account of the state of the subject through the year 2007. It is authoritative, comprehensive, accurate, thoughtful, and extremely well and carefully written. In many ways it can be considered the companion of L. L. Schumaker's well-known and classic monograph [Spline functions: basic theory, Wiley, New York, 1981; MR0606200 (82j:41001)], which covers univariate and tensor product splines. Recently, that book appeared in its third edition [Cambridge Univ. Press, Cambridge, 2007; MR2348176].
   There are 18 chapters, and about 360 references are quoted in the text. (There is also a reference in the preface to a much larger online bibliography.) Each chapter concludes with Remarks and detailed Historical Notes. The book can be used as a textbook for a graduate class, but it does not contain formal exercises.
   Specific covered topics include: triangulations and tetrahedral partitions, bi- and trivariate polynomials, Bernstein-Bézier form and techniques, approximation power of splines and polynomials, interpolation by splines and polynomials, dimensions of spline spaces, (nodal, local, stable) bases of spline spaces, minimal determining sets, macro elements, finite elements, box splines, splines on the sphere.
   If you need to know anything about multivariate splines this book will be your first and surest source of information for years to come.

Summary: "Macro-elements of arbitrary smoothness are constructed on Powell-Sabin triangle splits. These elements are useful for solving boundary-value problems and for interpolation of Hermite data. It is shown that they are optimal with respect to spline degree, and we believe they are also optimal with respect to the number of degrees of freedom. The construction provides local bases for certain superspline spaces defined over Powell-Sabin refinements. These bases are shown to be stable as a function of the smallest angle in the triangulation, which in turn implies that the associated spline spaces have optimal order approximation power.''

The authors present macro-elements (also called finite elements) of arbitrary smoothness on Clough-Tocher splits of triangles. The polynomial degree of these elements grows with the degree of smoothness but is as low as possible on the Clough-Tocher split. The construction provides local bases of certain spaces of smooth piecewise polynomial functions (splines) over triangles. The bases are stable and the associated spline spaces have optimal approximation order.

The simplest and very popular non-tensor product generalization of the cardinal $B$ $B$ -splines from the univariate to the bivariate settings is the class of box splines $B_{ l mn}$ $B_{ l mn}$ on the 3-direction mesh (with multiplicities $ l, m, n$ $l, m, n$ , respectively, for the three directions that formulate the uniform triangulation). In two independent papers by Riemenschneider and Shen, and by Stöckler, Ward, and the reviewer, both of which appeared in 1992, compactly supported semi-orthogonal wavelets $\psi^j_{lmn},\ j=1, 2, 3,$ $\psi^j_{lmn},\ j=1, 2, 3,$ corresponding to the box spline $B_{ l mn}$ $B_{ l mn}$ were constructed. However, as is well known, the duals of (nonorthogonal) semiorthogonal wavelets have infinite support. The objective of this paper is to give a formula for constructing compactly supported biorthogonal box-spline wavelets on the 3-direction mesh, as a generalization of the fundamental work of Cohen, Daubechies, and Feauveau, from the univariate to the bivariate setting. A MATHEMATICA computer program for computing low order examples is included as an appendix to the paper.

The authors consider spaces $S^r_d$ $S^r_d$ of $r$ $r$ times differentiable piecewise degree $d$ $d$ polynomial functions defined on a triangulation that is obtained from a quadrilateral tessellation by dividing each quadrilateral into four triangles. They show the following: The space $S^r_{3r}$ $S^r_{3r}$ has full approximation power (which is remarkable since a corresponding result does not hold on general triangulations), for $r=1,2$ $r=1,2$ these spaces can be used to reduce the complexity of spline spaces on ordinary triangulations, the spaces $S^r_{3r}$ $S^r_{3r}$ can be nested to allow a multi-resolution analysis, and the resulting special triangulations can be refined locally.

For a given triangulation $\Delta$ $\Delta$ of a bounded polygonal domain $\Omega$ $\Omega$ in $\bold R^2$ $\bold R^2$ the authors investigate the approximation power of spaces $S^r_d(\Delta)=\{s\in C^r(\Omega)\colon\ s|_T\in P_d,\ T\in\Delta\}$ $S^r_d(\Delta)=\{s\in C^r(\Omega)\colon\ s|_T\in P_d,\ T\in\Delta\}$ of splines of degree $d$ $d$ and smoothness $r$ $r$ , where $P_d$ $P_d$ denotes the space of polynomials of total degree $d$ $d$ . They prove that for $d\geq 3r+2$ $d\geq 3r+2$ , the space $S^r_d(\Delta)$ $S^r_d(\Delta)$ has optimal approximation order with respect to the uniform norm and the $L_p$ $L_p$ -norm $(1\leq p<\infty)$ $(1\leq p&lt;\infty)$ . To do this, a linear quasi-interpolation operator is constructed which approximates functions from Sobolev spaces and its derivatives to optimal order. The authors show that the approximation constants depend only on the smallest angle in the underlying triangulation $\Delta$ $\Delta$ , and the nature of the boundary of the domain. To prove this, a special super-spline space with a stable basis of local support is introduced. Aspects of so-called near-degenerate edges and near-singular vertices and the phenomenon of propagation are discussed in detail. The methods developed in this paper are different from those of C. K. Chui, D. Hong and R. Q. Jia [Trans. Amer. Math. Soc. 347 (1995), no. 9, 3301--3318; MR1311906 (96d:41012)], used for the uniform norm.

Summary: "We show how $C^2$ $C^2$ supersplines of degree six can be used to interpolate Hermite data at the vertices of a quadrangulation. We also present error bounds that show that our method has full approximation order seven, and compare its efficiency with other $C^2$ $C^2$ interpolation methods in the literature.''

Summary: "We show that if the scattered data over a polygonal domain can be quadrangulated, then the space of bivariate $C^1$ $C^1$ piecewise cubic polynomial functions on a triangulation obtained from the quadrangulation has the full approximation order. We point out that our method is more efficient than the Clough-Tocher scheme.''

Summary: "A vertex spline basis of the super-spline subspace $\widehat{ S}^r_d\coloneq S_d^{r, r+\lfloor (d-2r-1)/2\rfloor}(\Delta )$ $\widehat{ S}^r_d\coloneq S_d^{r, r+\lfloor (d-2r-1)/2\rfloor}(\Delta )$ of $S^r_d(\Delta )$ $S^r_d(\Delta )$ , where $d\ge 3r+2$ $d\ge 3r+2$ and $\Delta $ $\Delta$ is an arbitrary triangulation in $\bold R^2$ $\bold R^2$ , is constructed, so that the full approximation order of $d+1$ $d+1$ can be achieved via an approximation formula using this basis.''