Estimating unknown sparsity, sparse signal processing and proximal Newton-type methods

In this post I just collect a few papers that caught my attention in the last moth.

I begin with Estimating Unknown Sparsity in Compressed Sensing by Miles E. Lopes. The abstract reads

Within the framework of compressed sensing, many theoretical guarantees for signal reconstruction require that the number of linear measurements exceed the sparsity of the unknown signal . However, if the sparsity is unknown, the choice of remains problematic. This paper considers the problem of estimating the unknown degree of sparsity of with only a small number of linear measurements. Although we show that estimation of is generally intractable in this framework, we consider an alternative measure of sparsity , which is a sharp lower bound on , and is more amenable to estimation. When is a non-negative vector, we propose a computationally efficient estimator , and use non-asymptotic methods to bound the relative error of in terms of a finite number of measurements. Remarkably, the quality of estimation is dimension-free, which ensures that is well-suited to the high-dimensional regime where . These results also extend naturally to the problem of using linear measurements to estimate the rank of a positive semi-definite matrix, or the sparsity of a non-negative matrix. Finally, we show that if no structural assumption (such as non-negativity) is made on the signal , then the quantity cannot generally be estimated when .

It’s a nice combination of the observation that the quotient is a sharp lower bound for and that it is possible to estimate the one-norm and the two norm of a vector (with additional properties) from carefully chosen measurements. For a non-negative vector you just measure with the constant-one vector which (in a noisy environment) gives you an estimate of . Similarly, measuring with Gaussian random vector you can obtain an estimate of .

Then there is the dissertation of Dustin Mixon on the arxiv: Sparse Signal Processing with Frame Theory which is well worth reading but too long to provide a short overview. Here is the abstract:

Many emerging applications involve sparse signals, and their processing is a subject of active research. We desire a large class of sensing matrices which allow the user to discern important properties of the measured sparse signal. Of particular interest are matrices with the restricted isometry property (RIP). RIP matrices are known to enable efficient and stable reconstruction of sfficiently sparse signals, but the deterministic construction of such matrices has proven very dfficult. In this thesis, we discuss this matrix design problem in the context of a growing field of study known as frame theory. In the first two chapters, we build large families of equiangular tight frames and full spark frames, and we discuss their relationship to RIP matrices as well as their utility in other aspects of sparse signal processing. In Chapter 3, we pave the road to deterministic RIP matrices, evaluating various techniques to demonstrate RIP, and making interesting connections with graph theory and number theory. We conclude in Chapter 4 with a coherence-based alternative to RIP, which provides near-optimal probabilistic guarantees for various aspects of sparse signal processing while at the same time admitting a whole host of deterministic constructions.

By the way, the thesis is dedicated “To all those who never dedicated a dissertation to themselves.”

Further we have Proximal Newton-type Methods for Minimizing Convex Objective Functions in Composite Form by Jason D Lee, Yuekai Sun, Michael A. Saunders. This paper extends the well explored first order methods for problem of the type with Lipschitz-differentiable or simple to second order Newton-type methods. The abstract reads

We consider minimizing convex objective functions in composite form

where is convex and twice-continuously differentiable and is a convex but not necessarily differentiable function whose proximal mapping can be evaluated efficiently. We derive a generalization of Newton-type methods to handle such convex but nonsmooth objective functions. Many problems of relevance in high-dimensional statistics, machine learning, and signal processing can be formulated in composite form. We prove such methods are globally convergent to a minimizer and achieve quadratic rates of convergence in the vicinity of a unique minimizer. We also demonstrate the performance of such methods using problems of relevance in machine learning and high-dimensional statistics.

With this post I say goodbye for a few weeks of holiday.

 

Reading and writing abstracts

I read abstracts quite a lot and I also have to write them occasionally. Nowadays I usually write abstracts quite quickly and don’t think too much if the abstract is going to be good. This semester I am organizing a seminar for the graduate students and post docs in our department (we simply call this seminar “research seminar”) and especially have to collect the abstracts to make the announcements. Since all mathematical institutes here are involved, the topics vary a lot: abstract algebra, numerical linear algebra, mathematical physics or optimization. Hence, it may happen that I get abstracts which I can hardly access and I thought if it is always possible to write an abstract someone like me can understand. At this point I should probably explain what I mean by “understand”: I think that an abstract should allow to locate the field in which the talk will be situated. Moreover, I should understand what the objects of interests will be and what the role of these objects is in the field. Moreover, it would be good if I would be able to estimate how the topic of the talk is related to other fields of mathematics (especially to fields I am interested in).

Since the people who give talks in our research seminar are mostly quite early in their career I made the following experiment: When I received a new abstract I read it thoroughly and tried to understand it in the above sense. Usually there was something which I totally not got and I went ahead and replied to the speaker and asked very basic questions which I asked myself while reading the abstract; questions like “What are the object you talk about?” or “What can one do with these objects or results?”. The speakers then responded with a new version of the abstract and from my point of view this process always produced a way better abstract.

Hence, I started thinking about rules and tips to write a good abstract. From what I’ve written above, I tried to deduce some rules which I collect here:

• Avoid jargon. Although this sounds obvious, most abstracts contain jargon in one way or the other. Of course one can not avoid the use of specific terminology and technical terms but even then there is an easy check, if a technical term is appropriate: Try to find a definition on the internet – if you do not succeed within a few minutes you should find a different word. I’ll try to illustrate this with an example (which I randomly choose from arxiv.org on a topic which is quite far away from mine):

  On a convex body in a Euclidean space, we introduce a new variational formulation for its Funk metric, a Finsler metric compatible with the tautological Finsler structure of the convex body.

  I know what a convex body in Euclidean space is and I know what could be meant by a variational formulation; however, I had no idea what a Funk metric is – but it was not hard to find out that a Finsler structure is something like a “metric varying continuously from point to point”. Well, its still open to me, what the “tautological” Finsler structure of the convex body shall be, but this is something that I hope, a talk or paper could explain. This example is somehow borderline, since the additional explanation still leads to terms which are not all defined on Wikipedia or Wolfram MathWorld. But still, this sentence gives me something: The author studies the geometry of convex bodies and will come up with a variational formulation of a special metric.

• Use buzzwords. This may sound to contradict the precious point and in part it does. But beware that you can use a buzzword together with its explanation. Again, the example from the previous point works: “Funk metric” may be a buzzword and the explanation using the name “Finsler” is supposed to ring a bell (as I learned, it is related to Hilbert’s 23rd problem). This helps the readers to find related work and to remember what was the field you were working in.

• General to specific. In general it’s a good advice to work from general to specific. Start with a sentence which points in the direction of the field you are working in. So your potential audience will know from the beginning in which field your work is situated.
• Answer questions. If you think that your work answers questions, why not pose the questions in the abstract? This may motivate the readers to think by themselves and draw their interest to the topic.
• Don’t be afraid of layman’s terms. Although layman’s terms usually do not give an exact description and sometimes even are ridiculously oversimplified, they still help to form a mental picture.

Finally I’d like to repeat an advice which you can find in almost every other collection of tips on writing (e.g. here: Write, read, rewrite and reread your abstract. Repeat this procedure.