On a general class of matrix nearness problems (Q1176190)

The following problem is considered: Given a rectangular matrix A, determine a matrix \(\Delta\) of minimal norm and prescribed sparsity such that \(\text{rank}(A+\Delta)<\text{rank } A\). Describing the sparsity pattern by means of a generalized block decomposition into zero and possibly nonzero blocks one considers norms which are of the form \(\|\Delta\|=(f(\nu))^{1/\alpha}\), where \(f\) is a monotone gauge function and \(\nu=(\nu_ i)\) denotes the nonnegative vector whose components are the norms of the individual nonzero blocks in \(\Delta\). The norm for each block may be different, but is assumed to be separable (i.e., \(\nu_ i=\| uv^ T\|_{(i)}=\| u\|_{A_ i}\| v^ T\|^*_{B_ i}\), \(\|\cdot\|_{A_ i}\) a vector norm, \(\| \cdot\|^*_{B_ i}\) a dual vector norm for each rank one block \(uv^ T\)). It is shown that, provided the problem is solvable (i.e., the set of all \(\Delta\) such that \(\text{rank}(A+\Delta)<\text{rank }A\) is nonempty), it can be solved by considering a related (reduced) problem, involving less variables and only the vector norms \(\|\cdot\|_{A_ i}\) and \(\|\cdot\|_{B_ i}\). The description is then spezialized to matrix norms which separate into vector-\(\ell_ 2\)-norms, such as the spectral- (i.e. the \(\ell_ 2\)-operator) or the Frobenius norm. In that case it is possible to formulate stationary point conditions for the reduced problem. The procedure is illustrated by some numerical examples. The paper closes with a short section on the problem of finding a \(\Delta\) of minimal norm such that \(\text{rank}(A+\Delta)=\text{rank }A-d\), where \(d>0\) is prescribed.