Nuclear norm minimization

Let us assume that X is the adjacency matrix where each entry denotes interaction between a drug and target (1 if they interact, 0 otherwise). Unfortunately, we only observe this matrix partially because all interactions are not known. If M denotes the partially observed adjacency matrix, the mathematical relation between X and M is expressed as:

In the above equation, A denoted the sub-sampling operator, element-wise multiplied to X. It is nothing but a binary matrix or a mask that has 0’s where the interaction X has not been observed or is unknown and 1’s where they have been. The task is to recover X, given the observations M, and the sub-sampling mask A. It is known that X is of low-rank. Ideally, X should be recovered by (2).

Unfortunately, rank minimization is an NP-hard problem with doubly exponential complexity, therefore solving it directly is not feasible.

Traditionally, a low-rank matrix has been modeled as a product of a thin and a fat matrix and recovered using Matrix Factorization techniques [38]. But, Matrix Factorization is a bi-linear non-convex problem, therefore there is no guarantee for global convergence. In the past decade, mathematicians showed that the rank minimization problem can be relaxed by its convex surrogate (nuclear norm minimization) with provable guarantees [39, 40] This turns out to be a convex problem that can be solved by Semi-Definite Programming. More efficient solvers have also been proposed. Problem (2) is expressed as (3)

Here the nuclear norm (|| ||_*) is defined as the sum of singular values of data matrix X. It is the l₁ norm (sum of absolute values) of the singular values of X and is the tightest convex relaxation of the rank of the matrix, and hence its ideal replacement.

Here, (3) is a constrained formulation for the noiseless scenario, usually its relaxed version, (4) is solved.

One of the efficient solvers for Nuclear Norm minimization is the Singular value shrinkage (SVS) algorithm [47].

Algorithm 1 Singular value shrinkage

1: procedure Matrix-SVS(M, A, λ)

2:  Initialize: X = rand, a

3:   For loop, iterate (k)

4:    Bk=Xk−1+1aAT(M−A°Xk−1)

5:    Compute SVD of B: B_k = USV^T

6:    Soft threshold the singular values: Σ = soft(S, λ/2)

7:    X_k = UΣV^T

8:    Xk←Xk+

9:  End loop 1