January 2012

Today I write about sparse recovery of “multidimensional” signals. With “multidimensional” I mean something like this: A one-dimensional signal is a vector {x\in{\mathbb R}^n} while a two-dimensional signal is a matrix {x\in{\mathbb R}^{n_1\times n_2}}. Similarly, {d}-dimensional signal is {x\in{\mathbb R}^{n_1\times\cdots\times n_d}}. Of course, images as two-dimensional signals come time mind. Moreover, movies are three-dimensional, a hyperspectral 2D image (which has a whole spectrum attached to any pixel) is also three-dimensional, and time-dependent volume-data is four-dimensional.

Multidimensional data is often a challenge due the large amount of data. While the size of the signals is usually not the problem it is more the size of the measurement matrices. In the context of compressed sensing or sparse recovery the signal is measured with a linear operator, i.e. one applies a number {m} of linear functionals to the signal. In the {d}-dimensional case this can be encoded as a matrix {A\in {\mathbb R}^{m\times \prod_1^d n_i}} and this is where the trouble with the data comes in: If you have megapixel image (which is still quite small) the matrix has a million of columns and if you have a dense matrix, storage becomes an issue.

One approach (which is indeed quite old) to tackle this problem is, to consider special measurement matrices: If the signal has a sparse structure in every slice, i.e. every vector is of the form {x(i_1,\dots,i_{k-1},:,i_{k+1},\dots,i_d)} where we fix all but the {k}-th component, then the Kronecker product of measurement matrices for each dimension is the right thing.

The Kronecker product of two matrices {A\in{\mathbb R}^{m\times n}} and {B\in{\mathbb R}^{k\times j}} is the {mk\times nj} matrix

\displaystyle  A\otimes B = \begin{bmatrix} a_{11}B & \dots & a_{1n}B\\ \vdots & & \vdots\\ a_{n1}B & \dots & a_{nn}B \end{bmatrix}.

This has a lot to do with the tensor product and you should read the Wikipedia entry. Moreover, it is numerically advantageous not to build the Kronecker product of dense matrices if you only want to apply it to a given signal. To see this, we introduce the vectorization operator {\text{vec}:{\mathbb R}^{m\times n}\rightarrow{\mathbb R}^{nm}} which takes a matrix {X} and stacks its columns into a tall column vector. For matrices {A} and {B} (of fitting sizes) it holds that

\displaystyle  (B^T\otimes A)\text{vec}(X) = \text{vec}(AXB).

So, multiplying {X} from the left and from the right gives the application of the Kronecker product.

The use of Kronecker products in numerical linear algebra is fairly old (for example they are helpful for multidimensional finite difference schemes where you can build Kronecker products of sparse difference operators in respective dimensions). Recently, they have been discovered for compressed sensing and sparse recovery in these two papers: Sparse solutions to underdetermined Kronecker product systems by Sadegh Jokar and Volker Mehrmann and the more recent Kronecker Compressed Sensing by Marco Duarte and Rich Baraniuk.

From these papers you can extract some interestingly simple and nice theorems:

Theorem 1 For matrices {A_1,\dots A_d} with restricted isometry constant {\delta_K(A_1),\dots,\delta_K(A_d)} of order {K} it holds that the restricted isometry constant of the Kronecker product fulfills

\displaystyle  \max_i \delta_K(A_i) \leq \delta_K(A_1\otimes\cdots\otimes A_d) \leq \prod_1^d (1+\delta_K(A_i))-1.

Basically, the RIP constant of a Kronecker product is not better than the worst one but still not too large.

Theorem 2 For matrices {A_1,\dots, A_d} with columns normalized to one, it hold that the spark of their Kronecker product fulfills

\displaystyle  \text{spark}(A\otimes \dots\otimes A_d) = = \min_i\text{spark}(A_i).

Theorem 3 For matrices {A_1,\dots, A_d} with columns normalized to one, it hold that the mutual coherence of their Kronecker product fulfills

\displaystyle  \mu(A_1\otimes\dots\otimes A_d) = \max_i \mu(A_i).

Lately quite a discussion about journals, publishing and ranking has started, also in the mathematical community. As an entry to the discussion on the role of journals you may consider the post “How might we get to a new model of mathematical publishing?” by Timothy Gowers (and the follow-up “A more modest approach”) and also some entries on nuit blanche or the post “The problem with journals”. Recently, I found that the International Mathematical Union (IMU) has started a blog on related issues: The Blog On Mathematical Journals. In the first entry “BLOG on Mathematical Journals” Ingrid Daubechies and Barbara Lee Keyfitz describe the aim of this blog: “We invite the mathematical community to provide their views on the journal rating issue, and on whether IMU and ICIAM should formulate their own rating. Views on how to establish and update this rating would also be welcome.” Although the first entry only introduced the rating issue, two further posts discuss other topics related to publishing: What might be done about high prices of journals? and Beyond Journals.

In total, the current system of publication is criticized to several extends in the discussion and I’d like to add some remarks on the pricing and ranking issue in this post.

1. Pricing

I know that some journals have prices which seem high and I have heard a lot of people complaining about high journal prices (some of them just repeat what they have heard, but other are in charge of library budget). I myself can not judge if prices are too high or appropriate. However, Where I am it seems like the library is not too rich, but basically I have no problems to obtain the papers I’d like to read: Either they are available in published digital form or printed (by campus or national license), they are available at the authors websites (in their published form or in a preprint form), they are available in preprint form on some preprint server or, as a last resort, I ask the authors directly (and rarely I ask a colleague at a richer university to download the paper and send it…). So, access to results is not a problem for me and I think for nobody at a university, at least in Germany.

One complain is that the countries pay the private publishers, through the university budgets, for work which is done by their employees (the scientists). Well, but this seems ok, since the scientists are the “only” customers, and the customers pay for what a company delivers to them. This is comparable to other situations in which countries pay private companies. However, here (as in other cases) a non-profit company, run by the country, could do the same job. A specific issue is that the journals are totally international (e.g. the editorial boards are mostly formed by reputation in the respective field and not by nationality). Hence, a centralized system should be independent of the countries which makes a transition from a decentralized system based on companies difficult.

Moreover, publishing is not totally for free and it just not true that publishers do nothing for their money. Well, we TeX our papers ourselves, however, a good publisher has to do (and does) quite some editing both technically and linguistically, to get a polished and publishable paper. Also, do not forget that the publishers do a good job in maintaining databases, permanent and stable links and cross-referencing their content (do not point to free tools like Google Scholar here, they heavily depend on the good databases by the publishers). For me it seems difficult to judge if journals are overpriced. I just do not have enough information: How many staff is needed to maintain the publication of a journal? How is the access to articles in general (several journals allow to publish a pdf on your own website)? What are examples of bad practice and best practice (high price with no service, high price and great service, low price and good service…)?

2. Ranking and rating

The primary task of the IMU blog is the discussion of journal ratings. I am not sure about the differences between “rating” and “ranking” but as far as I understand, a ranking of things should at least answer the question “Which of these two items is better?” for all two items, while a rating should answer the question “How good is this item?” for every item. Then, a ranking of journals is, in my opinion, truly not desirable and not achievable. Well, I am sorry for this old analogy, but this is just comparing apples and oranges. Which one is better: FC Barcelona or the LA Lakers? The Simpsons or How I met Your Mother? An iPad or a Nintendo 3DS? A Hummer H2 or a Smart? Lufthansa or the London Underground? Jacket or trousers? Annals of Mathematics or Annals of Statistics? Annales Scientifiques de l’École Normale Supérieure or Mathematics of Operations Research? SIAM Journal on Numerical Analysis or Crelle’s Journal? I hope you’ve got my point…

But how about a rating? Isn’t it possible to say that a journal is top, average or below? Actually there is journal rating by the Australian Mathematical Society here (although they call it ranking…). There they rate the journals into categories A*, A, B and C (from good to bad). I checked the rating of some journals I know and published in and I have to confess that I mainly agree with the ratings of there journals (e.g. Inverse Problems is excellent, Current Development in Theory and Applications of Wavelets is mediocre).

There are a lot of comments to the post BLOG on Mathematical Journals most of them saying that it is inappropriate to reduce the “quality” of a journal to a single number or rate and this number will not be any better than Impact Factor rubbish (see e.g. the comment by Jean-Paul Allouche). Arieh Iserles made the point that ratings are already used and will be used in the future and a self-made rating will be better than the others. John Ball argues why arguing against all rating is the better alternative (and gives two examples in which organizations abandoned from using ratings or bibliometry).

Basically, I do not have to add anything new to the comments given in the post. My opinion is that rating is possible but both useless and dangerous. It is possible, since you can ask experienced mathematicians and you will get a reliable answer. It is useless, since you either know which journals are good or you can ask a colleague (which is basically the same reason as the previous one). It is dangerous, since it offers the possibility to form decisions on tenure or grants on these numbers and shifts the focus from what you publish to where you publish (see also the comment by Ivar Ekeland to this post).