Deterministic Completion of Rectangular Matrices Using Ramanujan Bigraphs -- I: Error Bounds and Exact Recovery

  • 2019-10-08 16:56:17
  • Shantanu Prasad Burnwal, Mathukumalli Vidyasagar
  • 0

Abstract

In this paper we study the matrix completion problem: Suppose $X \in {\mathbbR}^{n_r \times n_c}$ is unknown except for an upper bound $r$ on its rank. Bymeasuring a small number $m \ll n_r n_c$ of the elements of $X$, is it possibleto recover $X$ exactly, or at least, to construct a reasonable approximation of$X$? At present there are two approaches to choosing the sample set, namelyprobabilistic and deterministic. Probabilistic methods can guarantee the exactrecovery of the unknown matrix, but only with high probability. At presentthere are very few deterministic methods, and they mostly apply only to squarematrices. The focus in the present paper is on deterministic methods that workfor rectangular as well as square matrices, and where possible, can guaranteeexact recovery of the unknown matrix. We achieve this by choosing the elementsto be sampled as the edge set of an asymmetric Ramanujan graph or Ramanujanbigraph. For such a measurement matrix, we (i) derive bounds on the errorbetween a scaled version of the sampled matrix and unknown matrix; (ii) derivebounds on the recovery error when max norm minimization is used, and (iii)present suitable conditions under which the unknown matrix can be recoveredexactly via nuclear norm minimization. In the process we streamline someexisting proofs and improve upon them, and also make the results applicable torectangular matrices. This raises two questions: (i) How can Ramanujan bigraphsbe constructed? (ii) How close are the sufficient conditions derived in thispaper to being necessary? Both questions are studied in a companion paper.

 

Quick Read (beta)

Deterministic Completion of Rectangular Matrices
Using Ramanujan Bigraphs – I:
Error Bounds and Exact Recovery

Shantanu Prasad Burnwal and Mathukumalli Vidyasagar The authors are with the Indian Institute of Technology Hyderabad, Kandi, Telangana 502285, India. Emails: [email protected], [email protected] This research was supported by the Department of Science and Technology, and the Science and Engineering Research Board, Government of India.
Abstract

In this paper we study the matrix completion problem: Suppose Xnr×nc is unknown except for an upper bound r on its rank. By measuring a small number mnrnc of the elements of X, is it possible to recover X exactly, or at least, to construct a reasonable approximation of X? At present there are two approaches to choosing the sample set, namely probabilistic and deterministic. Probabilistic methods can guarantee the exact recovery of the unknown matrix, but only with high probability. At present there are very few deterministic methods, and they mostly apply only to square matrices. The focus in the present paper is on deterministic methods that work for rectangular as well as square matrices, and where possible, can guarantee exact recovery of the unknown matrix. We achieve this by choosing the elements to be sampled as the edge set of an asymmetric Ramanujan graph or Ramanujan bigraph. For such a measurement matrix, we (i) derive bounds on the error between a scaled version of the sampled matrix and unknown matrix; (ii) derive bounds on the recovery error when max norm minimization is used, and (iii) present suitable conditions under which the unknown matrix can be recovered exactly via nuclear norm minimization. In the process we streamline some existing proofs and improve upon them, and also make the results applicable to rectangular matrices.

This raises two questions: (i) How can Ramanujan bigraphs be constructed? (ii) How close are the sufficient conditions derived in this paper to being necessary? Both questions are studied in a companion paper.

1 Introduction

1.1 General Statement

Compressed sensing refers to the recovery of high-dimensional but low-complexity objects from a small number of linear measurements. Recovery of sparse (or nearly sparse) vectors, and recovery of high-dimensional but low-rank matrices are the two most popular applications of compressed sensing. The object of study in the present paper is the matrix completion problem, which is a special case of low-rank matrix recovery. The matrix completion problem has been getting a lot of attention because of its application to different areas such as image processing, sketching, quantum tomography, and recommendation systems (e.g., the Netflix problem). An excellent survey of the matrix completion problem can be found in [1].

1.2 Problem Definition

The matrix completion problem can be stated formally as follows: Suppose Xnr×nc is an unknown matrix that we wish to recover whose rank is bounded by a known integer r. Let [n] denote the set {1,,n} for each integer n. In the matrix completion problem, a set Ω[nr]×[nc] is specified, known as the sample set or measurement set. To be specific, suppose Ω={(i1,j1),,(im,jm)}, where |Ω|=m is the total number of samples. We are able to measure the values Xi,j for all (i,j)Ω. Equivalently, the set of measurements can be expressed as the Hadamard product11 1 Recall that the Hadamard product C of two matrices A,B of equal dimensions is defined by cij=aijbij for all i,j. EΩ.X where EΩ{0,1}nr×nc is defined by

(EΩ)ij={1if (i,j)Ω,0if (i,j)Ω.

From these measurements, and the information that rank(X)r, we aim to recovery X completely, or at least to construct a good approximation of X.

One possible approach to the matrix completion problem is to set

X^=argminZnr×ncrank(Z) s.t. EΩ.Z=EΩ.X. (1)

The above problem is a special case of minimizing the rank of an unknown matrix subject to linear constraints, and is therefore NP-hard [2]. Since the problem is NP-hard, a logical approach is to replace the rank function by its convex relaxation, which is the nuclear norm, or the sum of the singular values of a matrix, as shown in [3]. Therefore the convex relaxation of (1) is

X^:=argminZnr×ncZN s.t. EΩ.Z=EΩ.X. (2)

It is known that, when the elements of Ω are selected at random, the unique solution to (2) is the true but unknown matrix X, with high probability. Such results are reviewed in Section 2.

Another emerging trend is to use the so-called “max-norm” introduced in [4]. To define this norm, we begin by recalling that, if Uk×l, then an induced matrix norm is given by

U2:=maxx21Ux=maxi[k]ui2,

where ui denotes the i-th row of the matrix U. The max-norm of a matrix X is defined as

Xm=minX=UVU2V2. (3)

With this definition, an alternate approach to matrix completion is

X^:=argminZnr×ncZm s.t. EΩ.Z=EΩ.X. (4)

1.3 Contributions of the Present Paper

In the literature to date, most of the papers assume that the sample set Ω is chosen at random from [nr]×[nc], either without replacement as in [5], or with replacement [6]. The authors are aware of only two papers [7, 8] in which a deterministic procedure is suggested for choosing the sample set Ω as the edge set of a Ramanujan graph. (This concept is defined below).

In case Ω is chosen at random, it makes little difference whether the unknown matrix is square or rectangular. However, if Ω is to be chosen in a deterministic fashion, then the approach suggested in [7, 8] requires that the unknown matrix be square.22 2 Though the paper [7] uses the notation Xnr×nc, in the theorems it is assumed that nr=nc. The reason for this is that, while it is possible to define the notion of a Ramanujan bigraph (which would be required in the case of rectangular matrices), until now there is not a single explicit construction of such a graph, only some abstract formulas that are not explicitly computable [9, 10]. One of the main contributions of a companion paper is to present an infinite family of Ramanujan bigraphs; this is the first such explicit construcion. In the present paper, we prove bounds on how close the solution of (2) is to the true but unknown matrix. These bounds are an improvement on the available bounds in two different ways. First, these bounds are applicable for rectangular matrices, while existing deterministic methods do not apply to this case. Second, even in the case of square matrices, our bounds improve currently available bounds. These improvements are achieved though modifying the so-called “expander mixing lemma” for bipartite graphs, which is a result that is possibly of independent interest. Finally, we derive sufficient conditions under which the unique solution of (1) is the true but unknown matrix.

2 Literature Review

In [5], the authors point out that the formulations (1) or (2) do not always recover an unknown matrix. They illustrate this by taking X as the matrix with a 1 in the (1,1) position and zeros elsewhere. In this case, unless (1,1)Ω, the solution to both (1) and (2) is the zero matrix, which does not equal X. The difficulty in this case is that the matrix has high “coherence,” as defined next.

Definition 1.

Suppose XRnr×nc has rank r and the reduced singular value decomposition X=UΣV, where URnr×r, VRnc×r, and ΣRr×r is the diagonal matrix of the nonzero singular values of X. Let PU=UURnr×nr denote the orthogonal projection of Rnr onto URnr. Finally, let eiRnr denote the i-th canonical basis vector. Then we define

μ0(U):=nrrmaxi[nr]PU𝐞i22=nrrmaxi[nr]ui22, (5)

where ui is the i-th row of U. The quantity μ0(V) is defined analogously, and

μ0(X):=max{μ0(U),μ0(V)}. (6)

Next, define

μ1(X):=nrncrUV, (7)

It is shown in [5] that 1μ0(U)nrr. The upper bound is achieved if any canonical basis vector is a column of U. (This is what happens with the matrix with all but one element equalling zero.) The lower bound is achieved if every element of U has the same magnitude of 1/n, that is, a submatrix of a Walsh-Hadamard matrix.

To facilitate the statement of some known results in matrix completion, we reproduce from the literature two standard coherence assumptions on the unknown matrix X=UΣV.

  1. (A1).

    There are known upper bounds μ0,μ1 on μ0(X) and μ1(X) respectively.

  2. (A2).

    There is a constant θ such that

    kJnrdc(UkUk)-IrSθ,J[nr],|J|=dc, (8)
    kJncdr(VkVk)-IrSθ,J[nc],|J|=dr, (9)

    where Uk is shorthand for (Uk).

Assumption (A2) can be interpreted as follows: The relationship UU=Ir can be expressed as

k[nr](UkUk)=Ir.

Therefore, if |J| is sufficiently large, it can be expected that

kJnr|J|(UkUk)-IrS

would be small.

2.1 Probabilistic Sampling

There are two approaches to choosing the sample set Ω, namely probabilistic and deterministic. In the probabilistic approach the elements of Ω are chosen at random from [nr]×[nc]. In this setting one can further distinguish between two distinct situations, namely sampling from [nr]×[nc] with replacement or without replacement. If one were to sample m out of the nrnc elements of the unknown matrix X without replacement, then one is guaranteed that exactly m distinct elements of X are measured. However, the disadvantage is that the locations of the m samples are not independent, which makes the analysis quite complex. This is the approach adopted in [5].

Theorem 1.

(See [5, Theorem 1.1].) Draw

mCmax(n)5/4rlog(n) (10)

samples from [nr]×[nc] without replacement. Then with probability atleast 1-ζ where

ζ=cn-3 (11)

the recovered matrix X^ using (2) is be the unique solution. Here C,c are some universal constants that depend on μ, and n=max(nr,nc).

An alternative is to sample the elements of X with replacement. In this case the locations of the m samples are indeed independent. However, the price to be paid is that, with some small probability, there would be duplicate samples, so that after m random draws, the number of elements of X that are measured could be smaller than m. This is the approach adopted in [6]. On balance, the approach of sampling with replacement is easier to analyze.

Theorem 2.

(See [6, Theorem 2].) Assume without loss of generality that nrnc. Choose some constant β>1, and draw

m32max{μ12,μ0}r(nr+nc)βlog2(2nc) (12)

samples from [nr]×[nc] with replacement. Define X^ as in (2). Then, with probability at least equal to 1-ζ where

ζ=6log(nc)(nr+nc)2-2β+nc2-2β, (13)

the true matrix X is the unique solution to the optimization problem, so that X^=X.

2.2 Basic Concepts from Graph Theory

In contrast with probabilistic sampling, known deterministic approaches to sampling make use of the concept of Ramanujan graphs. For this reason, we introduce a bare minimum of graph theory. Further details about Ramanujan graphs can be found in [11, 12].

Suppose B{0,1}nr×nc. Then B can be interpreted as the biadjacency matrix of a bipartite graph with nr vertices on one side and nc vertices on the other. If nr=nc, then the bipartite graph is said to be balanced, and is said to be unbalanced if nrnc. The prevailing convention is to refer to the side with the larger (nc) vertices as the “left” side and the other as the “right” side. A bipartite graph is said to be left-regular with degree dc if every left vertex has degree dc, and right-regular with degree dr if every right vertex has degree dr. It is said to be (dr,dc)-biregular if it is both left- and right-regular with row-degree dr and column-degree dc. Obviously, in this case we must have that nrdr=ncdc. It is convenient to say that a matrix B{0,1}nr×nc is “(dr,dc)-biregular” to mean that the associated bipartite graph is (dr,dc)-biregular. The bipartite graph corresponding to B is defined to be a Ramanujan bigraph if

|σ2|dr-1+dc-1. (14)

2.3 Deterministic Sampling

The following result is claimed in [7].

Theorem 3.

(See [7, Theorem 4.2].) Suppose Assumptions (A1) and (A2) hold. Choose EΩ to be the adjacency matrix of d regular graph such that σ2(EΩ)Cd, and θ<1/6. Define X^ as in (2). With these assumptions, if

d36C2μ02r2, (15)

Then the true matrix X is the unique solution to the optimization problem (2).

However, there is one step in the proffered proof of the above theorem that does not appear to be justified. More details are given in the Appendix.

Theorems 1 and 2 pertain to nuclear norm minimization as in (2). In [8], an alternate set of bounds is obtained for max norm minimization as in (3). The matrix is assumed to be square, with dr=dc=d.

Theorem 4.

(See [8, Theorem 2].) Suppose EΩ is the adjacency matrix of a d-regular graph with second largest (in magnitude) eigenvalue equal to λ. Define X^ as in (3). Then

1n2X^-XF28KGλdXm2, (16)

where KG is Grothendieck’s constant, and F denotes the Frobenius norm of a matrix.

There is no closed-form formula for this constant, but it is known that

KGπ2log(1+2)1.78221.

See [13] for this and other useful properties of Grothendieck’s constant.

Theorems 1 and 2 on the one hand, and Theorem 4 on the other hand, have complementary strengths and weaknesses. Theorems 1 and 2 ensure the exact recovery of the unknown matrix via nuclear norm minimization. However, the bounds involve the coherence of the unknown matrix as well as its rank. In contrast, the bound in Theorem 4 is “universal” in that it does not involve either the rank or the coherence of the unknown matrix X, just its max norm. Moreover, the bound is on the Frobenius norm of the difference X^-X, and thus provides an “element by element” bound. On the other hand, there are no known results under which max norm minimization exactly recovers the unknown matrix.

3 New Results

In this section we state without proof the principal new results in the paper. The proofs are given in subsequent sections.

3.1 Rationale of Using Ramanujan Bigraphs

We begin by giving a rationale of why biadjacency matrices of Ramanujan bigraphs are useful as measurement matrices. Suppose we could choose EΩ=𝟏nr×nc, the matrix of all ones. Then EΩ.X=X, and we could recover X exactly from the measurements. However, this choice of EΩ corresponds to measuring every element of X, and there would be nothing “compressed” about this sensing. Now suppose that EΩ=B, the biadjacency matrix of a (dr,dc)-biregular graph. Then σ1=drdc is the largest singular value of B, with corresponding row and column singular vectors u1=(1/nr)𝟏nr and v1=(1/nc)𝟏nc. Let σ2 denote the second largest singular value of B. Then

B=σ1u1v1+B2, where B2S=σ2,

where S denotes the spectral norm of a matrix (i.e., its largest singular value). Using the formulas for u1 and v1 and rescaling shows that

nrncdrdcB=𝟏nr×nc+nrncdrdcB2.

This formula can be expressed more compactly by defining the constant α, as

α:=drdcnrnc=drnc=dcnr,

where the various equalities follow from the fact that nrdr=ncdc. One can think of α as the fraction of elements of the unknown matrix X that are sampled. Since 𝟏nr×nc.X=X, we see that

1αB.X=X+M.X,

where M=(1/α)B2. Therefore

1αB.X-XS=M.XS. (17)

Now note that

MS=σ2α=σ2nrncdrdc=σ2σ1nrnc.

Therefore, the smaller σ2 is compared to σ1, the better the approximation error is betwen (1/α)B.X and the unknown matrix X.33 3 Note that nr,nc are the dimensions of the unknown matrix and are therefore fixed. Now, a Ramanujan bigraph is one for which this ratio is as small as possible. It is shown in [14] that, if (dr,dc) are kept fixed while (nr,nc) are increased, subject of course to the constraint that nrdr=ncdc, then (14) gives the best possible upper bound on σ2.

3.2 Error bounds using deterministic sampling

Theorem 5 below provides an upper bound on the error between a scaled version of the measurement matrix EΩ.X an the true matrix X. It extends [7, Theorem 4.1] to rectangular matrices while at the same time providing a simpler proof. Note that there is no optimization involved in applying this bound.

Theorem 5.

Suppose the sampling set Ω comes from a (dr,dc)-regular bipartite graph, and let σ2 denote the second largest singular value of EΩ (and of course σ1=drdc is the largest singular value of EΩ). Suppose XRnr×nc is a matrix of rank r or less, and let μ0 denote its coherence as defined in (6). Then

1αEΩ.X-XSσ2σ1μ0rXS, (18)

where S denotes the spectral norm (largest singular value) of a matrix.

Remark: Observe that the bound in (18) is a product of two terms: σ2/σ1 which depends on the measurement matrix EΩ, and μ0rXS which depends on the unknown matrix X.

Corollary 1.

Suppose the sampling set Ω comes from a (dr,dc)- regular asymmetric Ramanujan graph, Then

1αEΩ.X-XSμ0r|1dr+1dc|XS. (19)

Theorem 6 below extends [8, Theorem 2] to rectangular matrices. (Note that the same theorem was also independently discovered in [15, Theorem 22].) Even for square matrices, the bound in Theorem 6 is smaller by a factor of two compared to that in [8, Theorem 2], stated here as Theorem 4. Note that, similarly to Theorem 4 but in contrast with Theorem 5, the bound in Theorem 6 does not involve the coherence of the unknown matrix, nor its rank. Moreover, the bound is on the Frobenius norm of the difference, and is therefore an “element by element” bound, unlike in Theorem 5.

Theorem 6.

Suppose the sampling set Ω comes from a (dr,dc)-regular bipartite graph, and let σ2 denote the second largest singular value of its biadjacency matrix.44 4 Note that biregularity implies that the largest singular value is drdc. Suppose X^ is a solution of (3). Then

1nrncX-X^F24KGσ2σ1Xm2 (20)

where F is the Frobenious norm, m is the max norm and KG is Grothendieck’s constant.

Corollary 2.

Suppose the sampling set Ω comes from a (dr,dc)- regular asymmetric Ramanujan graph, Then

1nrncX-X^F24KG|1dr+1dc|Xm2 (21)

3.3 Sufficient Condition for Exact Recovery

The next theorem presents a sufficient condition under which nuclear norm minimization as in (2) and sampling matrix from a Ramanujan bigraph leads to exact recovery of the unknown matrix. Note that [7, Theorem 4.2] claims to provide such a sufficient condition for square matrices. However, in the opinion of the authors, there is a gap in the proof, as discussed in the Appendix. Therefore Theorem 7 can be thought as the first result to prove exact recovery using nuclear norm minimization and a deterministic sampling matrix.

Theorem 7.

Suppose XRnr×nc is a matrix of rank r or less, and satisfies the incoherence assumptions A1 and A2 with constants μ0 and θ.55 5 Note that, unlike [5, 6], we do not require the constant μ1. Suppose EΩ{0,1}nr×nc is a biadjacency matrix of a (dr,dc) biregular graph Ω, and let σ2 denote the second largest singular value of matrix EΩ. Define

ϕ=σ2σ1μ0r, (22)

where σ1=drdc, and suppose that

θ+ϕ<1/2, (23)
(1+43r2)ϕ+θ<1. (24)

Then X is the unique solution of (2).

4 Proofs

In this section we give the proofs of various theorems in the previous section. Due to its length, the proof of Theorem 7 is given separately in the Appendix. We state a couple of lemmas that are used repeatedly in the sequel. Throughout we use the notation that if A is a matrix, then Ai,Aj denote the i-th row and j-th column of A respectively. The ij-th element of A is denoted by Aij.

4.1 Some Preliminary Results

Theorem 8.

Suppose MRnr×nc, ARnr×r, and BRnc×r. Suppose further that xRnr,yRnc. Then

x(M.(AB))y=k[r](x.Ak)M(Bk.y). (25)
Proof.

The proof follows readily by expanding the triple product. Note that

(AB)ij=k[r]AikBjk.

Therefore

x(M.(AB))y = i[nr]j[nc]xi(Mijk[r]AikBjk)yj
= k[r]i[nr]j[nc]xiAikMijBjkyj
= k[r](x.Ak)M(Bk.y),

as desired. ∎

Theorem 9.

Suppose M,A,B are as in Theorem 8. Suppose further that

Ai22a2,Bi22b2. (26)

Then

M.(AB)SabMS. (27)
Proof.

Recall that, for any matrix X, we have that

XS=maxx2=1,y2=1xXy.

In particular

M.(AB)S = maxx2=1,y2=1x(M.(AB))y
= maxx2=1,y2=1k[r](x.Ak)M(Bk.y),

where the last step follows from Theorem 8. Now fix x,y such that x2=1,y2=1. Then

x(M.(AB))yMSk[r]x.Ak2Bk.y2.

Therefore (27) is proved once it is established that, whenever x2=1,y2=1, it follows that

k[r]x.Ak2Bk.y2ab. (28)

To prove (28), apply Schwarz’ inequality to deduce that

k[r]x.Ak2Bk.y2 (k[r]x.Ak22)1/2 (29)
(k[r]Bk.y22)1/2.

Now

k[r]x.Ak22 = k[r]i[nr](xiAik)2
= i[nr]xi2(k[r]Aik2)
= i[nr]xi2Ai22
a2i[nr]xi2=a2.

By entirely similar reasoning, we get

k[r]Bk.y22b2.

Substituting these two bounds into (29) establishes (28) and completes the proof. ∎

4.2 Proof of Theorem 5

Proof.

As before, define

M:=(1/α)EΩ-𝟏nr×nc,

and recall that

M.X=(1/α)EΩ.X-X,MS=σ2α.

Now suppose X=UΓV is a singular value decomposition of X, where Γ=Diag(γ1,,γr). Define A=UΓ,B=V. Then X=AB. Moreover

k[r]Aik2 = k[r]Uik2γk2γ12k[r]Uik2
XS2μ0rnr,

because XS=γ1, and the definition of the coherence μ0. Similarly

k[r]Bik2=k[r]Bik2μ0rnc.

Now apply Theorem 9 with

c=XSμ0rnr,d=μ0rnc,

and note that αnrnc=drdc=σ1. Then (27) becomes

(1/α)EΩ.X-XSσ2σ1μ0rXS,

as desired. ∎

4.3 Proof of Theorem 6

The proof of Theorem 6 is based on the following extension of the expander mixing lemma from [16] for rectangular expander graphs, which might be of independent interest.

Lemma 1.

Let E be the adjacency matrix of an asymmetric (dr,dc) biregular graph with (nr,nc) vertices so that nrdr=ncdc, and σ1=drdc is the largest singular value of E. Let σ2 denote the second largest singular value of E. Then for all S[nr] and T[nc], we have:

||S|nr|T|nc-|(S,T)|||| (30)
σ2|||S||T|(1-|S|nr)(1-|T|nc)
= σ2σ1|S||T|nrnc(1-|S|nr)(1-|T|nc),

where |E(S,T)| is the number of edges between the two vertex sets S and T, and |E|=nrdr=ncdc=nrdrncdc is the total number of edges in the graph.

Remark: First we explain why this result is called the “expander mixing lemma.” Note that |S|/nr is the fraction of rows that are in S, while |T|/nc is the fraction of columns that are in T. If the total number of edges nrdr=ncdc were to be uniformly distributed, then the term on the left side of (30) would equal zero. Therefore the bound (30) estimates the extent to which the distribution of edges deviates from being uniform.

The above result extends [8, Theorem 8] which is adapted from [16, Lemma 2.5] to (dr,dc) regular Ramanujan graphs. Moreover, the bound given here is tighter, because of the presence of the two square-root terms on the right side. As |S|,|T| become larger, the square root terms tend to zero. No such term is present in [16, Lemma 2.5].

Proof.

Let 𝟏S,𝟏T denote the characterstic vectors of sets S,T respectively. Then

|(S,T)|=uS,vTEuv=𝟏SE𝟏T.

Write E=i=1rσiuivi, and note that, due to the biregularity of E, we have that u1=(1/nr)𝟏nr, v1=(1/nc)𝟏nc, and σ1=drdc. Next, write 𝟏S=iβiui+a and 𝟏T=jγjvj+b, where a,b belong to the row null space and column null space of E respectively. Note that β1=𝟏S,u1F=|S|/nr, and similarly γ1=|T|/nc. Then

|(S,T)|=(iβiui+a)E(jγjvj+b)=drdcnrnc|S||T|+i=2rσiβiγi.

Rearranging the above gives

|drdcnrnc|S||T|-|(S,T)||=|i=2rσiβiγi|σ2i=2r|βi||γi|. (31)

Next, by Schwarz’ inequality, it follows that

i=2r|βi||γi|(i=2rβi2)1/2(i=2rγi2)1/2.

Now note that

i=2rβi2=𝟏S22-α12=|S|-|S|2nr=|S|(1-|S|nr),

and similarly

i=2rγi2=|T|(1-|T|nc).

This implies that

|i=2rσiβiγi|σ2|S||T|(1-|S|nr)1/2(1-|T|nc)1/2. (32)

Substituting this into (31), dividing both sides by nrdrncdc=|| gives the first expression in (30). The second expression follows from σ1=drdc. ∎

Theorem 10.

Suppose RRnr×nc and Ω is the edge set of an asymmetric (dr,dc)-biregular graph. Then

|1nrncijRij-1|Ω|(i,j)ΩRij|σ2σ1KGRm (33)

where KG is Grothendieck’s constant.

Note that the same result is independently discovered in [15, Theorem 22].

Proof.

Let Mnr×nc be a rank 1 sign matrix with {1,-1} entries, and define its corresponding binary matrix by M¯=1/2(M+J), where J is a matrix with all ones. Because M is a rank 1 sign matrix, it can be expressed as 𝜷𝜸, where 𝜷{-1,1}nr and 𝜸{-1,1}nc. Define

S:={i[nr]:βi=1},T:={j[nc]:γj=1}.

Let 𝟏S represent the characterstic vector of set S. Let S[nr] and T[nc], and let Sc,Tc denote the complements of S,T in the sets [nr],[nc] respectively. Then 𝜷=𝟏S-𝟏Sc, 𝜸=𝟏T-𝟏Tc, and M¯=𝟏S𝟏T+𝟏Sc𝟏Tc. Therefore

|1nrnci,jMij-1|Ω|(i,j)ΩMij|=|1nrnci,j(2M¯ij-1)-1|Ω|(i,j)Ω(2M¯ij-1)|=2|1nrnci,jM¯ij-1|Ω|(i,j)ΩM¯ij|=2||S||T|+|Sc||Tc|nrnc-E(S,T)+E(Sc,Tc)|Ω||2||S||T|nrnc-E(S,T)|Ω||+2||Sc||Tc|nrnc-E(Sc,Tc)|Ω||(a)4σ2σ1(|S||T|nrnc|Sc||Tc|nrnc)(b)σ2σ1. (34)

Here, the inequality (a) comes from Lemma 1 and the inequality (b) comes from xy(1-x)(1-y)1/4, where equality holds when x=y and x=(1-x).

Any real matrix Rnr×nc can be expressed as a sum of rank-1 sign matrices in the form R=iνiMi. Define

Rν:=mini|νi| s.t. R=iνiMi,

where the number of terms in the summation is unspecified. As stated in [8, Theorem 7] the max-norm can be related to this new norm ν via

XmXνKGXm. (35)

Therefore

|1nrnci,jRij-1|Ω|(i,j)ΩRij|=|kνk(1nrnci,jMkij-1|Ω|(i,j)ΩMkij)|k|νk||1nrnci,jMkij-1|Ω|(i,j)ΩMkij|(a)σ2σ1k|νk|(b)σ2σ1KGRm

where Mkij are the (i,j)-th elements of Mk for all k, (a) comes from (34), and (b) comes from (35). ∎

Proof.

(Of Theorem 6.) If R=(X-X^).(X-X^) then,

|1nrnci,j(Xij-X^ij)2-1|Ω|(i,j)Ω(Xij-X^ij)2|=|1nrnci,j(Xij-X^ij)2|=X-X^F2,

because xij=x^ij for all (i,j)Ω. Since the max norm is multiplicative under Hadamard product, we have

Rm(X-X^)m2(Xm+X^m)2=4Xm2.

Substituting both relationships into (33) gives the desired result. ∎

The proof of Theorem 7 is given in the Appendix.

5 Conclusions and Future Work

In this paper we have studied the matrix completion problem with emphasis on choosing the elements to be sampled in a deterministic fashion. We do this by choosing the sample matrix to equal the biadjacency matrix of a Ramanujan bigraph. We have derived (i) a bound on the error between a scaled version of the measured matrix, (ii) a bound on the error between the true matrix and an estimate constructed via max norm minimization, and (iii) a sufficient condition that guarantees exact recovery of the unknown matrix using nuclear norm minimization. In the process, we improve the so-called “expander mixing lemma” by a factor of two, and also present very streamlined proofs. Note that the same result is independently discovered in [15, Theorem 22].

We believe that we have presented the very first correct result on exact recovery using nuclear norm minimization and a deterministic sampling pattern. An earlier paper [7, Theorem 4.2] claims a similar result, but there is one step in the proof that we believe is not justified. This is elaborated in the Appendix.

The sufficient condition given here is very restrictive. It requires that the degree of the Ramanujan graph should be Ω(r3) where r is the rank of the matrix to be recovered. Turning this around, our result implies that given a Ramanujan graph of degree d, we can guarantee exact recovery only when r=O(d1/3). This naturally raises two questions: (i) How can one construct Ramanujan graphs and Ramanujan bigraphs of very high degree, and (ii) how close is the sufficient condition derived here to being necessary? These questions are studied in a companion paper. A preview of the companion paper can be found in [17]. To summarize briefly, numerical simulations show that Ramanujan graphs of degree d can accurately complete square matrices when the rank r is no larger than 0.3d. Of course, as yet there is no theory to back up these numerical results. More details will be presented in the companion paper.

References

  • [1] M. A. Davenport and J. Romberg, “An overview of low-rank matrix recovery from incomplete observations,” IEEE J. of Selected Topics in Signal Processing, vol. 10, no. 4, pp. 608–622, June 2016.
  • [2] B. Recht, M. Fazel, and P. Parrilo, “Guaranteed minimum rank solutions to linear matrix equations via nuclear norm minimization,” SIAM Review, vol. 52(3), pp. 471–501, 2010.
  • [3] M. Fazel, H. Hindi, and S. P. Boyd, “A rank minimization heuristic with application to minimum order system approximation,” in Proceedings of the American Control Conference, 2001, pp. 4734–4739.
  • [4] N. Srebro and A. Shraibman, “Rank, trace-norm and max-norm,” in 18th Annual Conference on Computational Learning Theory, 2005, pp. 545–560.
  • [5] E. Candès and B. Recht, “Exact matrix completion via convex optimization,” Foundations of of Computational Mathematics, vol. 9, pp. 717–772, 2008.
  • [6] B. Recht, “A simpler approach to matrix completion,” Journal of Machine Learning Research, vol. 12, pp. 3413–3430, 2011.
  • [7] S. Bhojanapalli and P. Jain, “Universal matrix completion,” in Proceedings of The 31st International Conference on Machine Learning, 2014, pp. 1881–1889.
  • [8] E. Heiman, G. Schechtman, and A. Shraibman, “Deterministic algorithms for matrix completion,” Random Structures and Algorithms, pp. 1–13, 2013.
  • [9] C. Ballantine and D. Ciubotaru, “Ramanujan bigraphs associated with SU(3) over a p-adic field,” Proceedings of the Amererican Mathematical Society, vol. 139, no. 6, pp. 1939–1953, 2011.
  • [10] C. Ballantine, B. Feigon, R. Ganapathy, J. Kool, K. Maurischat, and A. Wooding, “Explicit construction of Ramanujan bigraphs,” in Women in Numbers in Europe.   Springer Verlag, 2015, pp. 1–16.
  • [11] M. R. Murty, “Ramanjuan graphs,” Journal of the Ramanujan Mathematical Society, vol. 18, no. 1, pp. 1–20, 2003.
  • [12] G. Davidoff, P. Sarnak, and A. Valette, Elementary Number Theory, Group Theory, and Ramanujan Graphs.   Cambridge University Press, 2003.
  • [13] S. Friedland, L.-H. Lim, and J. Zhang, “An elementary and unified proof of Grothendieck’s inequality,” arXiv:1711.10595v3.
  • [14] K. Feng and W.-C. W. Li, “Spectra of hypergraphs and applications,” Journal of number theory, vol. 60, no. 1, pp. 1–22, 1996.
  • [15] G. Brito, I. Dumitriu, and K. D. Harris, “Spectral gap in random bipartite biregular graphs and applications,” arxiv:1804.07808, 2018.
  • [16] S. Hoory, N. Linial, and A. Widgerson, “Expander graphs and their application,” Bulletin of the American Mathematical Society (New Series), vol. 43, no. 4, pp. 439–561, October 2006.
  • [17] S. P. Burnwal and M. Vidyasagar, “Deterministic completion of rectangular matrices using asymmetric Ramanujan graphs,” arXiv:1908.00963, pp. 1–29, 2019.

Appendix: Proof of Theorem 7

This appendix contains the proof of Theorem 7. Suppose X=UΣV is the unknown matrix of rank r or less that is to be recovered, where Unr×r, Vnc×r, and Σ is diagonal of dimensions r×r. Throughout this appendix, the symbols U and V denote only these matrices and nothing else.

We begin with a preliminary result.

Lemma 2.

Suppose EΩ{0,1}nr×nc is a (dr,dc)-biregular sampling matrix, let U,V be as above, and let θ be as defined in (8) and (9).

  1. 1.

    For arbitrary Bnc×r, define

    F:=(1/α)UEΩ.(UB)-B. (36)

    Then

    FFθBF. (37)
  2. 2.

    For arbitrary Cnr×r, define

    G=(1/α)EΩ.(CV)V-C. (38)

    Then

    GFθCF. (39)
Proof.

Fix i[r],j[nc]. Then

Fji = (F)ij=𝐞iF𝐞j
= (1/α)𝐞iUEΩ.(UB)𝐞j-Bji.

Let us focus on the first term after ignoring the factor of 1/α. From Theorem 8, specifically (25), we get

𝐞iUEΩ.(UB)𝐞j = UiEΩ.(UB)𝐞j
= k[r](Ui.Uk)EΩ(Bk.𝐞j).

Now observe that Bk.𝐞j=Bjk𝐞j, so that EΩ(Bk.𝐞j)=(EΩ)jBjk. Therefore

𝐞iUEΩ.(UB)𝐞j=k[r](Ui.Uk)(EΩ)jBjk.

For this fixed j, define

𝒩(j)={l[nr]:(EΩ)lj=1},

and note that |𝒩(j)|=dc due to regularity. Then, for fixed k[r], we have

(Ui.Uk)(EΩ)j = l𝒩(j)UliUlk
= [l𝒩(j)UlUk]ik.

Therefore

(F)ij = (1/α)𝐞iUEΩ.(UB)𝐞j-Bji
= (1/α)k[r][l𝒩(j)UlUk]ikBjk-Bji
= ([(1/α)l𝒩(j)UlUl-Ir]B)ij.

By (8), the matrix inside the square brackets has spectral norm θ. Therefore

(F)j2θ(B)j2,j[nr].

Taking the norm squared and summing over all j proves (37), after noting that a matrix and its transpose have the same Frobenius norm. This establishes Item (1).

To prove Item (2), we use Item (1). Note that (X.Y)=X.Y. So (38) is equivalent to

G=(1/α)VEΩ.(VC)-C.

Now every column of EΩ (or every row of EΩ) contains dr ones. Therefore (39) follows from (37). ∎

Next, define 𝒯nr×nc to be the subspace spanned by all matrices of the form UB and CV. It is easy to show that the projection operator 𝒫𝒯 equals

𝒫𝒯Z = UUZ+ZVV-UUZVV
= UUZ+UUZVV
= UUZVV+ZVV,

where UU=Inr-UU and VV=Inc-VV.

The heart of the proof consists of establishing that, under suitable conditions that guarantee the existence of a “dual certificate,” the unknown matrix X is the unique solution to (1). This theorem is roughly similar to [6, Theorem 2].

Lemma 3.

Suppose there exists a YRnr×nc such that

  1. 1.

    Y belongs to the image of EΩ., that is Yij=0(i,j)Ω.

  2. 2.

    Y satisfies

    𝒫𝒯Y-UVFα32,𝒫𝒯(Y)S<34. (40)

Suppose further that the operator norm of (1/α)PTEΩ.-I when restricted to the subspace T is no larger than 1/2. In other words

(1/α)𝒫𝒯EΩ.Z-ZF(1/2)ZF,Z𝒯. (41)

Under these assumptions, for any ΔRnr×nc{0} such that EΩ.Δ=0, we have that

X+ΔN>XN, (42)

so that X^=X is the unique solution to (1).

Proof.

Suppose EΩ.Δ=0, so that EΩ.ΔF=0. Then

EΩ.𝒫𝒯ΔF2 =EΩ.𝒫𝒯Δ,𝒫𝒯ΔF
=𝒫𝒯EΩ.𝒫𝒯Δ-α𝒫𝒯Δ,𝒫𝒯ΔF
+α𝒫𝒯Δ,𝒫𝒯ΔF
(a)α𝒫𝒯ΔF2-α/2𝒫𝒯ΔF2
=α/2𝒫𝒯ΔF2,

where (a) follows from (41). Now, since EΩ.ΔF=0, we have EΩ.𝒫𝒯ΔF=EΩ.𝒫𝒯ΔF. Therefore,

𝒫𝒯ΔN 𝒫𝒯ΔFEΩ.𝒫𝒯ΔF (43)
α/2𝒫𝒯ΔF

Note that (43) implies that 𝒫𝒯ΔN>0. Suppose that 𝒫𝒯ΔN=0. Then (43) implies that 𝒫𝒯ΔF=0, and in turn Δ=𝒫𝒯Δ+𝒫𝒯Δ=0, which is a contradiction.

Next, recall that for any matrix M, it is true that

MN=maxU,VUV,MF

over all matrices U,V with orthogonal columns. In particular, for a particular Δ, it is possible to choose U,V such that [UU], [VV] have orthogonal columns, and

UV,𝒫𝒯ΔF=𝒫𝒯ΔN.

For such a choice, we have

X+ΔN (a) UV+UV,X+ΔF
=(b) XN+UV+UV,ΔF
=(c) XN+UV+UV,ΔF
 -Y,ΔF
= XN+UV-𝒫𝒯Y,𝒫𝒯ΔF
 +UV-𝒫𝒯Y,𝒫𝒯ΔF
(d) XN-UV-𝒫𝒯YF𝒫𝒯ΔF
 +𝒫𝒯ΔN-𝒫𝒯YS𝒫𝒯ΔN
XN-α/32𝒫𝒯ΔF
+ (1-𝒫𝒯YS)𝒫𝒯ΔN, (45)

where (a) follows from the characterization of the nuclear norm, (b) follows from UV,XF=0, (c) follows from Y,ΔF=0, and (d) follows from Hölder’s inequality, Now it follows from (40) and (43) that

(1-𝒫𝒯YS)𝒫𝒯ΔN > (1/4)𝒫𝒯ΔN
α/32𝒫𝒯ΔF,

where we use the fact that 𝒫𝒯ΔN>0. Substituting this fact into the last equation in (Appendix: Proof of Theorem 7) shows that X+ΔN>XN. ∎

The proof of Theorem 7 consists of showing that, under the stated hypotheses, there exists a Y that satisfies the conditions of Lemma 3. This is achieved through some preliminary lemmas.

Suppose that Z𝒯. Then

Z=𝒫𝒯Z=UUZ+UUZVV.

Thus one can write Z=UB+CV, where

B=UZ,C=UUZV. (46)

Throughout, we use the symbols B and C only as defined above.

Lemma 4.

Suppose EΩ{0,1}nr×nc is a (dr,dc)-biregular sampling matrix, and that ZT. Define, as before,

B=UZ,C=UUZV, (47)

so that Z=UB+CV. Next, define

Z¯:=(1/α)P𝒯EΩ.Z-Z, (48)
B¯=UZ¯,C¯=UUZ¯. (49)

Let μ0,θ,σ1,σ2 be as before. Then

B¯FθBF+σ2σ1μ0rCF, (50)
C¯Fσ2σ1μ0rBF+θCF. (51)

Remark: The above two relations can be expressed compactly as

[B¯FC¯F][θϕϕθ][BFCF], (52)

where, as in (22), we have

θ=θ,ϕ=σ2σ1μ0r, (53)
Proof.

We establish (50), and the proof of (51) is entirely similar.

The definition of 𝒫𝒯 makes it clear that

U𝒫𝒯Y=UY,UU𝒫𝒯Y=UUY,Ynr×nc.

Therefore

B¯=U((1/α)EΩ.(UB)-UB)+(1/α)UEΩ.(CV),

because UC=0. Define B¯=B¯1+B¯2, where

B¯1 = U((1/α)EΩ.(UB)-UB)
= (1/α)UEΩ.(UB)-B,
B¯2=(1/α)UEΩ.(CV).

Then it follows from Lemma 2 that

B¯1FθBF. (54)

To estimate B¯2F=B¯2F, we proceed as follows:

(B¯2)i=𝐞iB¯2=(1/α)UiEΩ.(CV),
(B¯2)i2 = maxync,y2=1(B¯2)iy
= maxy2=1(1/α)UiEΩ.(CV)y.

Fix a ync such that y2=1 but otherwise arbitrary. Then it follows by Theorem 8 that

(1/α)UiEΩ.(CV)y=(1/α)k[r](Ui.Ck)EΩ(Vk.y).

Now UiCk, so that Ui.CK𝟏nr. Therefore

(Ui.Ck)EΩ(Vk.y)σ2Ui.Ck2Vk.y2,k[r],
(1/α)UiEΩ.(CV)y σ2αk[r]Ui.Ck2Vk.y2 (55)
σ2α(k[r]Ui.Ck22)1/2
(k[r]Vk.y22)1/2,

where we use Schwarz’ inequality in the last step.

Now we can bound the second term as follows:

k[r]Vk.y22 = k[r]l[nc]Vlk2yl2
= l[nc]yl2k[r]Vlk2
μ0rncl[nc]yl2=μ0rnc,

where in the last step we use the definition of the coherence μ0. Substituting this bound into (55) gives

(B¯2)i22σ22α2μ0rnck[r]Ui.Ck22,
B¯2F2 = B¯2F2=i[nr](B¯2)i22 (56)
σ22α2μ0rnci[r]k[r]Ui.Ck22.

Now the last term can be bounded in a manner analogous to the above. We have that

i[r]k[r]Ui.Ck22 = i[r]k[r]l[nr]Uli2Clk2
= k[r]l[nr]Clk2i[r]Uli2
μ0rnrk[r]l[nr]Clk2
= μ0rnrCF2.

Substituting this bound in (56) gives

B¯2F2σ22α2(μ0r)2nrncCF2=(σ2σ1μ0r)2CF2.

Taking square roots of both sides gives

B¯2Fσ2σ1μ0rCF=ϕCF,
B¯FB¯1F+B¯2FθBF+ϕCF,

which is (50). The proof of (51) is entirely similar. ∎

Lemma 5.

Suppose EΩ{0,1}nr×nc is a (dr,dc)-biregular sampling matrix, that ZT, and define

Z¯:=(1/α)P𝒯EΩ.Z-Z, (57)

Then

Z¯F(θ+ϕ)ZF, (58)

where θ,ϕ are defined in (50) and (51) respectively.

Remark: The above lemma can be stated as follows: The map Z(1/α)P𝒯EΩ.Z-Z, when restricted to 𝒯, has an operator norm θ+ϕ.

Proof.

Define, as before,

B=UZ,C=UUZV,
B¯=UZ¯,C¯=UUZ¯,

so that Z=UB+CV, Z¯=UB¯+C¯V. Note that

UB,CVF=tr(BUCV)=0,

because UC=0. Therefore

ZF2 = UBF2+CVF2+2UB,CVF
= UBF2+CVF2=BF2+CF2,

because left multiplication by U and right multiplication by V preserve the Frobenius norm. Similarly

Z¯F2=B¯F2+C¯F2.

Now it is easy to verify that the spectral norm of the matrix in (52) is θ+ϕ. Therefore

Z¯F2 = B¯F2+C¯F2(θ+ϕ)2(BF2+CF2)
= (θ+ϕ)2ZF2.

This is the desired conclusion. ∎

Proof.

(Of Theorem 7.) At last we come to the proof of the theorem itself. Recall from Lemma 3 that X is the unique solution of (2) provided the following conditions hold: First, there exists a Ynr×nc that satisfies the following conditions:

  1. 1.

    Y belongs to the image of EΩ., that is Yij=0(i,j)Ω.

  2. 2.

    Y satisfies

    𝒫𝒯Y-UVFα32, (59)
    𝒫𝒯(Y)S<34. (60)

Second, the operator norm of (1/α)𝒫𝒯EΩ.-I when restricted to the subspace 𝒯 is no larger than 1/2. Lemma 5 shows that the above operator norm is θ+ϕ. Therefore if (23) holds, then this condition is satisfied. So it remains to construct a suitable Y.

We do this as follows: Define W0=UV, and define Wi recursively as

Wi=Wi-1-(1/α)𝒫𝒯EΩ.Wi-1, (61)
Yp=i=0p-1(1/α)EΩ.Wi. (62)

Then it is obvious that each Yp belongs to the image of EΩ. So the proof is complete once it is shown that Y satisfies the two conditions (59) and (60).

We begin with (59). Note that

(1/α)𝒫𝒯EΩ.Wi=Wi-Wi+1.

So

𝒫𝒯Yp=i=0p-1(Wi-Wi+1)=W0-Wp.

Therefore

𝒫𝒯Yp-W0F=WpF(θ+ϕ)pW0F,

where the last step follows from Lemma 5. Therefore, for sufficiently large p (which could be computed, but it is not necessary), if we choose Y=Yp, we have that

𝒫𝒯Y-UVF=𝒫𝒯Yp-W0Fα32,

which is (59).

To establish (60) and complete the proof, we reason as follows:

𝒫𝒯(Y) = 𝒫𝒯[i=0p-1(1/α)EΩ.Wi]
= 𝒫𝒯[i=0p-1[(1/α)EΩ.Wi-Wi]],

because Wi𝒯 and hence 𝒫𝒯Wi=0. Therefore

𝒫𝒯(Y)S = 𝒫𝒯[i=0p-1[(1/α)EΩ.Wi-Wi]]S
(a) [i=0p-1[(1/α)EΩ.Wi-Wi]]S
(b) i=0p-1(1/α)EΩ.Wi-WiS
(c) ϕi=0p-1WiS
(d) ϕi=0p-1WiF.

Here (a) follows because the spectral norm is submultiplicative and the spectral norm of P𝒯=1, (b) follows from the triangle inequality, (c) is a consequence of Theorem 5 and in particular (18), and (d) follows from the fact that the spectral norm is no larger than the Frobenius norm. Now we apply the recursion bound from Lemma 4. It states that, if we define

Bi=UWi,Ci=UUWiV,

then

[Bi+1FCi+1F][θϕϕθ][BiFCiF]. (63)

Now at i=0, we have that W0=UV=UB0+C0V with B0=(1/2)V, C0=(1/2)U. Since the columns of U and of V are normalized, and there ar r columns in each matrix, we have that

[B0FC0F]=r2[11].

Now note that [1  1] is an eigenvector of the matrix in (63), with eigenvalue θ+ϕ. Thus applying (63) recursively leads to

[BiFCiF]r2(θ+ϕ)i[11].

So

WiF=(BiF2+CiF2)1/2r2(θ+ϕ)i,
ϕi=0p-1WiF ϕi=0p-1r2(θ+ϕ)i
ϕi=0r2(θ+ϕ)i
= ϕr211-(θ+ϕ).

Now it is routine algebra to show that (24) can be rewritten as follows:

(1+43r2)ϕ+θ<1ϕr211-(θ+ϕ)<34.

Hence (60) also holds. This shows that Y satisfies the requisite conditions, and as a consequence, X is the unique solution to (2). ∎

We conclude the Appendix by pointing out an error in the proof of [7, Theorem 4.2]. The proof of this theorem is based on a recursion Lemma [7, Lemma 7.3], which is analogous to Lemma 4. It is assumed in the proof of Lemma [7, Lemma 7.3] that if the unknown matrix is expressed as X=UΣV and if we represent UU=(Inr-UU), then

|Ui,Uj| = |Ui,Uj|ij
|Ui,Uj|ifi=j

In order to prove [7, Theorem 4.2], the authors use

i[r]j[nr]Ui,Uj2=i[r]j[nr]Ui,Uj2,

which in turn implies Ui22=Ui22. However, in reality Ui22+Ui22=1. Therefore the incoherence property cannot be applied for Ui22, as used in their paper. Similar reasoning is used for V which is not correct. It is of course possible that the theorem itself is correct.