Simultaneous robust subspace recovery and semi-stability of quiver representations (Q2662209)

The authors investigate simultaneous robust subspace recovery, i.e., given an \(m\)-tuple of data sets \(\mathcal{X}^j:=\{v^j_1, \ldots, v^j_n\} \subseteq \mathbb{R}^{d_j}\), where \(j \in [m]=\{1,2,\ldots, m \}\), investigate the existence of an effective way to find an \(m\)-tuple of subspaces \((T_1, \ldots, T_m)\) with \(T_j \leq \mathbb{R}^{d_j}\), with \(j \in [m]\), such that \[ |\mathcal{I}_T|> \frac{\displaystyle{\sum_{j=1}^m} \dim T_j}{D} \cdot n, \] where \(\mathcal{I}_T = \{i \in [n] : v^j_i \in T_j \mbox{ for all } j \in [m]\}\) and \(D=\displaystyle{\sum_{j=1}^{m}} d_j\). One says that \(\mathcal{X}\) admits a lower-dimensional subspace structure if there exists a simultaneous robust subspace recovery solution for \(\mathcal{X}\). When \(m=1\), this is a central problem in robust subspace recovery where the optimal balance between robustness and efficiency is the key. For \(m>1\), this problem is related to the Hilbert-Mumford numerical criterion for semistability of representations of quivers. The authors prove the following (Theorem 2, page 214): let \(Q\) be a quiver without oriented cycles and let \((V, \sigma)\) be a quiver datum, defined over the rational numbers, such that \(\sigma \cdot \dim V=0\). Then there exist deterministic polynomial-time algorithms to check whether \(V\) is \(\sigma\)-semi-stable or not, and assuming that \(Q\) is a bipartite quiver (not necessarily complete) and \(\sigma\) is nowhere zero, there exists a deterministic polynomial time algorithm that constructs a subrepresentation \(W \leq V\) such that \(\text{disc}(V, \sigma)=\sigma \cdot \dim W\). In particular, if \(\sigma\cdot \dim W=0\), then \(V\) is \(\sigma\)-semi-stable. Otherwise, \(W\) is an optimal witness to \(V\) not being \(\sigma\)-semi-stable.