SIAM News Blog

From SIAM Review: Research Spotlights

By Evelyn Sander

The latest SIAM Review's Research Spotlights section contains two papers. The first of these is “Splines Are Universal Solutions of Linear Inverse Problems with Generalized TV Regularization," by Michael Unser, Julien Fageot, and John Paul Ward. The paper shows that for certain minimization problems in the \(L_1\) norm or total variation seminorm over a continuous domain, there exist spline solutions. Further, these solutions have fewer points of discontinuity (knots) than there are measurements. Careful attention is given to the presentation of a particularly useful case of this theorem, namely, that of sampling and compressed sensing, as used in the reconstruction of biomedical images, or more generally in the recovery of a signal from a sparse set of measurements. This work is a step along the way towards a universality result for spline solutions, and thus has the potential to change methods of analysis and discretization of such problems. It will be of interest to those interested both in the theory for minimization problems and those interested in applications of such problems in applied mathematics and beyond.

The second paper in this section, “The Nonnegative Rank of a Matrix: Hard Problems, Easy Solutions," by Yaroslav Shitov, presents an elementary linear algebra technique based on the nonnegative rank of a matrix. The nonnegative rank of a matrix \(A\) is the minimum number of nonnegative rank-one matrices required to sum to \(A\). This paper demonstrates that this rank is \(NP\)-hard to compute, as was previously shown using other techniques in 1993 by Jiang and Ravikumar and in 2009 by Vavasis. In 1993, Cohen and Rothblum asked whether it is possible to write a nonnegative rank \(k\) matrix as a sum of \(k\) rational nonnegative rank-one matrices. The problem had remained open since that time. This paper demonstrates that the answer to this question is, in general, no: it contains an example of a \(21 \times 21\) nonnegative rank-one matrix which cannot be decomposed using rational nonnegative rank-one matrices. Note that this paper appeared on the arXiv simultaneously with another paper which also solved the Cohen--Rothblum problem. Although the paper is only seven pages long, it manages to give a detailed account of the methods used. It will be of primary interest to those in numerical linear algebra. However, since it uses elementary techniques, it is accessible to readers outside the field.

Evelyn Sander is a professor of mathematics at George Mason University. She is the section of editor of the Research Spotlights section of SIAM Review. 
blog comments powered by Disqus