## A list of $$\|\cdot\|_{\infty \rightarrow 1}^*$$ problems

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).