Recall our old friend the \(\|\cdot\|_{\infty \rightarrow 1}^*\) norm (from the first version of this website, which I still haven’t gotten around to merging into the current iteration). Given a matrix \(\mat{A},\) it is a measure of the energy in the smallest expansion of \(\mat{A}\) in terms of rank one sign matrices:
\[
\|\mat{A}\|_{\infty \rightarrow 1}^* = \inf\left\{\sum_i d_i \,:\, \mat{A} = \sum_i d_i \vec{u}_i \vec{v}_i, \right\}
\]
where \(\{\vec{u}_i, \vec{v}_i\}\) is a collection of sign vectors. Note that the number of sign vectors necessary to achieve this minimum is not known a priori.
This is an interesting norm both intrinsically (as a potential source of factor models in statistics and machine learning) and because of its relations to other norms. See these slides for details.
An estimate of \(\|\cdot\|_{\infty \rightarrow 1}^*\) to within a multiplicative factor of about \(1.783\) can be obtained using a semidefinite program, but I suspect it’s NP hard to compute \(\|\cdot\|_{\infty \rightarrow 1}^*\) exactly (because \(\|\cdot\|_{\infty \rightarrow 1}^*\) is the trace dual of the \(\|\cdot\|_{\infty \rightarrow 1}\) norm, which is known to be NP-hard to compute — if the latter is also APX-hard, which I’m not sure of either way, then that means you definitely couldn’t compute \(\|\cdot\|_{\infty \rightarrow 1}^*\) efficiently in polynomial time). However, more interesting is the question of approximately obtaining the factorization corresponding to \(\|\cdot\|_{\infty \rightarrow 1}^*\): there doesn’t seem to be a good way to obtain such an approximate factorization from the SDP that gives the approximation of \(\|\cdot\|_{\infty \rightarrow 1}^*\), but maybe there’s a clever way to do so that I haven’t seen.
Other interesting questions abound: can we characterize \(\|\cdot\|_{\infty \rightarrow 1}^*\) or the number of rank 1 matrices needed to obtain the corresponding decomposition from a randomly chosen matrix (say i.i.d. Gaussian entries)? What if we just want probability bounds on the number of rank 1 matrices in the decomposition of a randomly chosen matrix?
I think the latter question is probably the easiest to answer of all posed here (except maybe coming up with an SDP-based approximate factorization).