text: [17] P. Harrison and S. Zertal. Queueing models with maxima of service times. In Computer Per- formance Evaluation. Modelling Techniques and Tools. 13th International Conference, TOOLS 2003, volume 2794 of Lecture Notes in Computer Science, pages 152–168. Springer, 2003. [18] P.R. Jelenkovi´c and M. Olvera-Cravioto. Implicit renewal theory and power tails on trees. Adv. Appl. Prob., 44(2):528–561, 2012. [19] P.R. Jelenkovi´c and M. Olvera-Cravioto. Implicit renewal theory for trees with general weights. Stochastic Process. Appl., 122(9):3209–3238, 2012. [20] P.R. Jelenkovi´c and M. Olvera-Cravioto. Maximums on trees. Stochastic Process. Appl., 125:217–232, 2015. [21] L. Kantorovich and G. Rubinstein. On a space of completely additive functions. Vestn. Leningr. Univ. Math., 13(7):52–59, 1958. [22] F.I. Karpelevich, M.Ya. Kelbert, and Yu.M. Suhov. Higher-order Lindley equations. Stochastic Process. Appl., 53:65–96, 1994. [23] F.P. Kelly. One-dimensional circuit-switched networks. Ann. Appl. Prob., 15(3):1166–1179, 1987. [24] A. Lebrecht, N.J. Dingle, and W.J. Knottenbelt. A response time distribution model for zoned raid. In 15th International Conference, ASMTA 2008, Lecture Notes in Computer Science, pages 144–157. Springer, 2008. [25] A. Lebrecht and W.J. Knottenbelt. Response time approximations in fork-join queues. 23rd Annual UK Performance Engineering Workshop (UKPEW), 2007. [26] M. Lin, J. Tan, A. Wierman, and L. Zhang. Joint optimization of overlapping phases in MapReduce. In Performance Evaluation, 2013, volume 70, pages 720–735, 2013. [27] R. Nelson and A.N. Tantawi. Approximate analysis of fork/join synchronization in parallel queues. IEEE Transactions on Computers, 37:739–743, 1988. [28] V. Nguyen. Processing networks with parallel and sequential tasks: heavy traﬃc analysis and brownian limits. Ann. Appl. Prob., 3(1):28–55, 1993. [29] U. R¨osler. The weighted branching process. Dynamics of complex and irregular systems (Bielefeld, 1991), pages 154–165, 1993. Bielefeld Encounters in Mathematics and Physics VIII, World Science Publishing, River Edge, NJ. [30] L. Ru¨shendorf. The Wasserstein distance and approximation theorems. Z. Wahrscheinlichkeit- stheorie verw. Gebiete, 70:117–129, 1985. [31] J. Tan, X. Meng, and L. Zhang. Delay tails in MapReduce scheduling. In Proceedings of the 12th ACM SIGMETRICS/PERFORMANCE joint international conference on Measurement and Modeling of Computer Systems, pages 5–16, 2012. [32] A. Thomasian. Analysis of fork/join and related queueing systems. ACM Computing Surveys, 47(2):17:1–17:71, 2014. 36

text: P.

text: Harrison

text: and

text: S.

text: Zertal.

text: Queueing

text: models

text: with

text: maxima

text: of

text: service

text: times.

text: In

text: Computer

text: Per-

text: formance

text: Evaluation.

text: Modelling

text: Techniques

text: and

text: Tools.

text: International

text: Conference,

text: TOOLS

text: volume

text: of

text: Lecture

text: Notes

text: in

text: Computer

text: Science,

text: pages

text: Springer,

text: P.R.

text: Jelenkovi´c

text: and

text: M.

text: Olvera-Cravioto.

text: Implicit

text: renewal

text: theory

text: and

text: power

text: tails

text: on

text: trees.

text: Adv.

text: Appl.

text: Prob.,

text: P.R.

text: Jelenkovi´c

text: and

text: M.

text: Olvera-Cravioto.

text: Implicit

text: renewal

text: theory

text: for

text: trees

text: with

text: general

text: weights.

text: Stochastic

text: Process.

text: Appl.,

text: P.R.

text: Jelenkovi´c

text: and

text: M.

text: Olvera-Cravioto.

text: Maximums

text: on

text: trees.

text: Stochastic

text: Process.

text: Appl.,

text: L.

text: Kantorovich

text: and

text: G.

text: Rubinstein.

text: On

text: a

text: space

text: of

text: completely

text: additive

text: functions.

text: Vestn.

text: Leningr.

text: Univ.

text: Math.,

text: F.I.

text: Karpelevich,

text: M.Ya.

text: Kelbert,

text: and

text: Yu.M.

text: Suhov.

text: Higher-order

text: Lindley

text: equations.

text: Stochastic

text: Process.

text: Appl.,

text: F.P.

text: Kelly.

text: One-dimensional

text: circuit-switched

text: networks.

text: Ann.

text: Appl.

text: Prob.,

text: A.

text: Lebrecht,

text: N.J.

text: Dingle,

text: and

text: W.J.

text: Knottenbelt.

text: A

text: response

text: time

text: distribution

text: model

text: for

text: zoned

text: raid.

text: In

text: International

text: Conference,

text: ASMTA

text: Lecture

text: Notes

text: in

text: Computer

text: Science,

text: pages

text: Springer,

text: A.

text: Lebrecht

text: and

text: W.J.

text: Knottenbelt.

text: Response

text: time

text: approximations

text: in

text: fork-join

text: queues.

text: Annual

text: UK

text: Performance

text: Engineering

text: Workshop

text: (UKPEW),

text: M.

text: Lin,

text: J.

text: Tan,

text: A.

text: Wierman,

text: and

text: L.

text: Zhang.

text: Joint

text: optimization

text: of

text: overlapping

text: phases

text: in

text: MapReduce.

text: In

text: Performance

text: Evaluation,

text: volume

text: pages

text: R.

text: Nelson

text: and

text: A.N.

text: Tantawi.

text: Approximate

text: analysis

text: of

text: fork/join

text: synchronization

text: in

text: parallel

text: queues.

text: IEEE

text: Transactions

text: on

text: Computers,

text: V.

text: Nguyen.

text: Processing

text: networks

text: with

text: parallel

text: and

text: sequential

text: tasks:

text: heavy

text: traﬃc

text: analysis

text: and

text: brownian

text: limits.

text: Ann.

text: Appl.

text: Prob.,

text: U.

text: R¨osler.

text: The

text: weighted

text: branching

text: process.

text: Dynamics

text: of

text: complex

text: and

text: irregular

text: systems

text: (Bielefeld,

text: pages

text: Bielefeld

text: Encounters

text: in

text: Mathematics

text: and

text: Physics

text: VIII,

text: World

text: Science

text: Publishing,

text: River

text: Edge,

text: NJ.

text: L.

text: Ru¨shendorf.

text: The

text: Wasserstein

text: distance

text: and

text: approximation

text: theorems.

text: Z.

text: Wahrscheinlichkeit-

text: stheorie

text: verw.

text: Gebiete,

text: J.

text: Tan,

text: X.

text: Meng,

text: and

text: L.

text: Zhang.

text: Delay

text: tails

text: in

text: MapReduce

text: scheduling.

text: In

text: Proceedings

text: of

text: the

text: ACM

text: SIGMETRICS/PERFORMANCE

text: joint

text: international

text: conference

text: on

text: Measurement

text: and

text: Modeling

text: of

text: Computer

text: Systems,

text: pages

text: A.

text: Thomasian.

text: Analysis

text: of

text: fork/join

text: and

text: related

text: queueing

text: systems.

text: ACM

text: Computing

text: Surveys,


text: [33] A. Thomasian and A.N. Tantawi. Approximate solutions for M/G/1 fork/join synchronization. In WSC 1994, pages 361–368, 1994. [34] I. Tsimashenka, W.J. Knottenbelt, and P.G. Harrison. Controlling variability in split-merge systems and its impact on performance. Ann. Oper. Res., 2014. [35] E. Varki. Mean value technique for closed fork-join networks. In ACM SIGMETRICS, pages 103–112, 1999. [36] E. Varki. Response time analysis of parallel computer and storage systems. IEEE Transactions on Parallel and Distributed Systems, 12:1146–1161, 2001. [37] S. Varma. Heavy and light traﬃc approximations for queues with synchronization constraints. PhD thesis, Dept. Electrical Engineering, Univ. Maryland, 1990. [38] S. Varma and A.M. Makowski. Interpolation approximations for symmetric fork-join queues. In Performance 1993, pages 245–265, 1994. [39] C. Villani. Optimal transport, old and new. Springer, New York, 2009. [40] W. Whitt. Blocking when service is required from several facilities simultaneously. AT&T Technical Journal, 64(8):1807–1985, 1985. [41] W. Whitt. Stochastic-Process Limits. Springer, New York, 2002. [42] M. Zaharia, D. Borthakur, J.S. Sarma, K. Elmeleegy, S. Shenker, and I. Stoica. Job scheduling for multiuser MapReduce clusters. Technical Report UCB/EECS-2009-55, EECS Department, University of California, Berkeley, 2009. 37

label: reference

text: A.

text: Thomasian

text: and

text: A.N.

text: Tantawi.

text: Approximate

text: solutions

text: for

text: fork/join

text: synchronization.

text: In

text: WSC

text: pages

text: I.

text: Tsimashenka,

text: W.J.

text: Knottenbelt,

text: and

text: P.G.

text: Harrison.

text: Controlling

text: variability

text: in

text: split-merge

text: systems

text: and

text: its

text: impact

text: on

text: performance.

text: Ann.

text: Oper.

text: Res.,

text: E.

text: Varki.

text: Mean

text: value

text: technique

text: for

text: closed

text: fork-join

text: networks.

text: In

text: ACM

text: SIGMETRICS,

text: pages

text: E.

text: Varki.

text: Response

text: time

text: analysis

text: of

text: parallel

text: computer

text: and

text: storage

text: systems.

text: IEEE

text: Transactions

text: on

text: Parallel

text: and

text: Distributed

text: Systems,

text: S.

text: Varma.

text: Heavy

text: and

text: light

text: traﬃc

text: approximations

text: for

text: queues

text: with

text: synchronization

text: constraints.

text: PhD

text: thesis,

text: Dept.

text: Electrical

text: Engineering,

text: Univ.

text: Maryland,

text: S.

text: Varma

text: and

text: A.M.

text: Makowski.

text: Interpolation

text: approximations

text: for

text: symmetric

text: fork-join

text: queues.

text: In

text: Performance

text: pages

text: C.

text: Villani.

text: Optimal

text: transport,

text: old

text: and

text: new.

text: Springer,

text: New

text: York,

text: W.

text: Whitt.

text: Blocking

text: when

text: service

text: is

text: required

text: from

text: several

text: facilities

text: simultaneously.

text: AT&T

text: Technical

text: Journal,

text: W.

text: Whitt.

text: Stochastic-Process

text: Limits.

text: Springer,

text: New

text: York,

text: M.

text: Zaharia,

text: D.

text: Borthakur,

text: J.S.

text: Sarma,

text: K.

text: Elmeleegy,

text: S.

text: Shenker,

text: and

text: I.

text: Stoica.

text: Job

text: scheduling

text: for

text: multiuser

text: MapReduce

text: clusters.

text: Technical

text: Report

text: EECS

text: Department,

text: University

text: of

text: California,

text: Berkeley,


text: as a method of performing matrix completion, or in general low rank matrix recovery tasks. However, all of these results may be classiﬁed as being in the uniform sampling regime. To this end, recently [4] established × that (1) can exactly recover an n n square matrix M of rank-r from Θ(nr log2 n) samples as long as the { } sampling distribution p and M’s row and column leverage scores µ (M), ν (M) n respectively, satisﬁes (cid:18) (cid:19) i j i,j=1 the following inequality: ≥ (µ (M) + ν (M))r log2(2n) ∈ × p min c i j , 1 for all (i, j) [n] [n], (2) ij 0 n for some universal constant c . With (2) the quantitative nature between the degree of non-uniformity of 0 the sampling distribution p and the corresponding coherence statistics of the matrix M has been established. Consider now a diﬀerent scenario, one in which the sampling distribution p and the underlying matrix’s { } { } leverage scores µ (M) n1 , ν (M) n2 do not align according to (2). One technique to remedy this i i=1 j j=1 (cid:55)→ situation is to design a transformation M M¯ so that we may adjust the leverage scores to align with ∈ the sampling distribution p. Following [5, 14] we choose weights of the form R := diag(R , . . . , R ) R × ∈ R × 1(cid:55)→ n1 n1 n1, C := diag(C1, . . . , Cn2) n2 n2. Using these parameterized weights, we will use M RMC as our transformation which will adjust leverage scores of M. In [14] a weighted nuclear norm objective was proposed. Following [5, 4], we will be considering the following weighted nuclear norm optimization problem: (cid:107) (cid:107) ∈ M¯ = argmin RXC ∗ subject to X = M , for (i, j) Ω. (3) ∈R × ij ij X n1 n2 In [4] exact recovery guarantees for (3) were established for weights R, C which were deﬁned in terms of × the true sampling distribution p, which we state for the square n n case: × Theorem 2.1. Let M = (M ) be an n n matrix of rank-r, and suppose that its elements M are observed ij ⊂ × ≤ ≤ij· · · ≤ only over a subset of elements Ω [n] [n]. Without loss of generality, assume R R R and ≤ ≤ · · · ≤ 1 2 n C1 C2 Cn.−There−exists(cid:32)a universal constant c0∈such×that M(cid:33) ≥is th−e unique optimum to (3) with probability at least 1 5(2n) 10 provided that for all (i, j) [n] [n], p n 10 and: ij (cid:80) (cid:80) ≥ R2 C2 pij c0 (cid:98)(cid:48)(n/(µi0r)(cid:99) R2(cid:48) + (cid:98)((cid:48)n/(µj0r)(cid:99) C2(cid:48) log2(2n). (4) i =1 i j =1 j S S Note that for monotonically increasing weights R, C the corresponding support sets , are merely (cid:98) (cid:99) r c the ﬁrst n/(µ r) indices, respectively. 0 For the remainder of the article, we shall assume that our sampling distribution p has a product form ∈ × p = prpc for all (i, j) [n ] [n ]. Furthermore, we will consider the following two-stage sampling model: ij i j 1 2 • Stage 1 (Empirical Sampling Distribution): We sample the distribution p with m times independently with replacement, but the corresponding entries of the data matrix M are not revealed to us. In other words, we are sampling the sampling distribution, but not the underlying matrix M. • Stage 2 (Sampling the Matrix): We then, independent of the ﬁrst stage, sample the matrix M using ∈ × the independent Bernoulli model for each entry (i, j) [n ] [n ]. 1 2 Note that this two stage sampling models allows one to sample the sampling distribution p without revealing the entries of M. In this manner we may design weights R, C which depend on the empirical sampling distribution pˆand obtain matrix completion guarantees for these weights in the usual (stage two) independent Bernoulli sampling model that has been typically used in the matrix completion literature. In this article we present stage one sampling bounds which will allow pˆ to be used as an empirical proxy for p to design weights R, C for (3) and obtain exact recovery with high probability. To this end, we establish the following two empirical estimation lemmas, which will serve as the foundation to our matrix completion guarantees. The ﬁrst is a one sided large deviation bound: 3 ##LTLine## ##LTLine## ##LTLine##

text: as

label: paragraph

text: a

text: method

text: of

text: performing

text: matrix

text: completion,

text: or

text: in

text: general

text: low

text: rank

text: matrix

text: recovery

text: tasks.

text: However,

text: all

text: of

text: these

text: results

text: may

text: be

text: classiﬁed

text: as

text: being

text: in

text: the

text: uniform

text: sampling

text: regime.

text: To

text: this

text: end,

text: recently

text: established

text: that

text: can

text: exactly

text: recover

text: an

text: n

text: n

text: square

text: matrix

text: M

text: of

text: rank-r

text: from

text: Θ(nr

text: n)

text: samples

text: as

text: long

text: as

text: the

text: sampling

text: distribution

text: p

text: and

text: M’s

text: row

text: and

text: column

text: leverage

text: scores

text: µ

text: (M),

text: ν

text: (M)

text: n

text: respectively,

text: satisﬁes

label: equation

text: i

text: j

text: the

text: following

text: inequality:

text: (µ

text: (M)

text: ν

text: (M))r

text: p

text: min

text: c

text: i

text: j

text: for

text: all

text: (i,

text: j)

text: [n]

text: [n],

text: ij

text: n

text: for

text: some

text: universal

text: constant

text: c

text: With

text: the

text: quantitative

text: nature

text: between

text: the

text: degree

text: of

text: non-uniformity

text: of

text: the

text: sampling

text: distribution

text: p

text: and

text: the

text: corresponding

text: coherence

text: statistics

text: of

text: the

text: matrix

text: M

text: has

text: been

text: established.

text: Consider

text: now

text: a

text: diﬀerent

text: scenario,

text: one

text: in

text: which

text: the

text: sampling

text: distribution

text: p

text: and

text: the

text: underlying

text: matrix’s

text: leverage

text: scores

text: µ

text: (M)

text: ν

text: (M)

text: do

text: not

text: align

text: according

text: to

text: One

text: technique

text: to

text: remedy

text: this

text: i

text: j

text: situation

text: is

text: to

text: design

text: a

text: transformation

text: M

text: M¯

text: so

text: that

text: we

text: may

text: adjust

text: the

text: leverage

text: scores

text: to

text: align

text: with

text: the

text: sampling

text: distribution

text: p.

text: Following

text: we

text: choose

text: weights

text: of

text: the

text: form

text: R

text: diag(R

text: R

text: R

text: R

text: C

text: Using

text: these

text: parameterized

text: weights,

text: we

text: will

text: use

text: M

text: RMC

text: as

text: our

text: transformation

text: which

text: will

text: adjust

text: leverage

text: scores

text: of

text: M.

text: In

text: a

text: weighted

text: nuclear

text: norm

text: objective

text: was

text: proposed.

text: Following

text: we

text: will

text: be

text: considering

text: the

text: following

text: weighted

text: nuclear

text: norm

text: optimization

text: problem:

text: M¯

text: argmin

text: RXC

text: subject

text: to

text: X

text: M

text: for

text: (i,

text: j)

text: Ω.

text: ∈R

text: ij

text: ij

text: X

text: In

text: exact

text: recovery

text: guarantees

text: for

text: were

text: established

text: for

text: weights

text: R,

text: C

text: which

text: were

text: deﬁned

text: in

text: terms

text: of

text: the

text: true

text: sampling

text: distribution

text: p,

text: which

text: we

text: state

text: for

text: the

text: square

text: n

text: n

text: case:

text: Theorem

text: Let

text: M

text: (M

text: be

text: an

text: n

text: n

text: matrix

text: of

text: rank-r,

text: and

text: suppose

text: that

text: its

text: elements

text: M

text: are

text: observed

text: ij

text: ≤ij·

text: only

text: over

text: a

text: subset

text: of

text: elements

text: Ω

text: [n]

text: [n].

text: Without

text: loss

text: of

text: generality,

text: assume

text: R

text: R

text: R

text: and

text: n

text: universal

text: constant

text: ≥is

text: th−e

text: unique

text: optimum

text: to

text: with

text: probability

text: at

text: least

text: provided

text: that

text: for

text: all

text: (i,

text: j)

text: [n]

text: [n],

text: p

text: n

text: and:

text: ij

text: pij

text: i

text: i

text: j

text: j

text: S

text: S

text: Note

text: that

text: for

text: monotonically

text: increasing

text: weights

text: R,

text: C

text: the

text: corresponding

text: support

text: sets

text: are

text: merely

text: r

text: c

text: the

text: ﬁrst

text: n/(µ

text: r)

text: indices,

text: respectively.

text: For

text: the

text: remainder

text: of

text: the

text: article,

text: we

text: shall

text: assume

text: that

text: our

text: sampling

text: distribution

text: p

text: has

text: a

text: product

text: form

text: p

text: prpc

text: for

text: all

text: (i,

text: j)

text: [n

text: [n

text: Furthermore,

text: we

text: will

text: consider

text: the

text: following

text: two-stage

text: sampling

text: model:

text: ij

text: i

text: j

text: Stage

text: (Empirical

text: Sampling

text: Distribution):

text: We

text: sample

text: the

text: distribution

text: p

text: with

text: m

text: times

text: independently

text: with

text: replacement,

text: but

text: the

text: corresponding

text: entries

text: of

text: the

text: data

text: matrix

text: M

text: are

text: not

text: revealed

text: to

text: us.

text: In

text: other

text: words,

text: we

text: are

text: sampling

text: the

text: sampling

text: distribution,

text: but

text: not

text: the

text: underlying

text: matrix

text: M.

text: Stage

text: (Sampling

text: the

text: Matrix):

text: We

text: then,

text: independent

text: of

text: the

text: ﬁrst

text: stage,

text: sample

text: the

text: matrix

text: M

text: using

text: the

text: independent

text: Bernoulli

text: model

text: for

text: each

text: entry

text: (i,

text: j)

text: [n

text: [n

text: Note

text: that

text: this

text: two

text: stage

text: sampling

text: models

text: allows

text: one

text: to

text: sample

text: the

text: sampling

text: distribution

text: p

text: without

text: revealing

text: the

text: entries

text: of

text: M.

text: In

text: this

text: manner

text: we

text: may

text: design

text: weights

text: R,

text: C

text: which

text: depend

text: on

text: the

text: empirical

text: sampling

text: distribution

text: pˆand

text: obtain

text: matrix

text: completion

text: guarantees

text: for

text: these

text: weights

text: in

text: the

text: usual

text: (stage

text: two)

text: independent

text: Bernoulli

text: sampling

text: model

text: that

text: has

text: been

text: typically

text: used

text: in

text: the

text: matrix

text: completion

text: literature.

text: In

text: this

text: article

text: we

text: present

text: stage

text: one

text: sampling

text: bounds

text: which

text: will

text: allow

text: pˆ

text: to

text: be

text: used

text: as

text: an

text: empirical

text: proxy

text: for

text: p

text: to

text: design

text: weights

text: R,

text: C

text: for

text: and

text: obtain

text: exact

text: recovery

text: with

text: high

text: probability.

text: To

text: this

text: end,

text: we

text: establish

text: the

text: following

text: two

text: empirical

text: estimation

text: lemmas,

text: which

text: will

text: serve

text: as

text: the

text: foundation

text: to

text: our

text: matrix

text: completion

text: guarantees.

text: The

text: ﬁrst

text: is

text: a

text: one

text: sided

text: large

text: deviation

text: bound:

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: We may repeat the analysis for the column case, where we choose t = α min ∈ pc, then analogously: j [n2] j | − | ≥ ≤ − Pr[ pˆc pc α min pc] 2 exp( 2(α min pc)2m). (27) j j ∈ j ∈ j j [n2] j [n2] ∈ | − | ≥ ∈ For any i [n ] let Er denote the event that pˆr pr α min ∈ pr and for any j [n ] let Ec denote | 1− | ≥i i i i [n1] i 2 j the event that pˆc pc α min ∈ pc. By (26), ((cid:18)27) and the Union Bound we have that: (cid:19) (cid:2) j j j [n2] j (cid:3) ≤ − − Pr For some (i, j) the event Er or Ec occurs 2 n exp( 2(α min pr)2m) + n exp( 2(α min pc)2m i j 1 ∈ i 2 ∈ j ≤ −i [n1] ∧ j [n2] 2(n + n ) exp( 2(α min pr min pc)2m). (28) 1 2 ∈ i ∈ j i [n1] j [n2] − − ∧ Observe that (28) immediately yields that with probability at least 1 2(n +n ) exp( 2(α min ∈ pr ∈ × 1 2 i [n1] i min ∈ pc)2m) for any (i, j) [n ] [n ] we have that the two following bounds hold: j [n2] j 1 2 | − | ≤ pˆr pr α min pr, (29) i i ∈ i | − | ≤ i [n1] pˆc pc α min pc. (30) j j ∈ j j [n2] The bound (29) is equivalent to the following: − ≤ − ≤ α min pr pˆr pr α min pr, ∈ i i i ∈ i i [n1] i [n1] ∈ and the above inequality yields that for any i [n ]: 1 1 ≤ ≤ 1 pˆr pr − pˆr. (31) 1 + α i i 1 α i ∈ Similarly (30) implies that for any j [n ]: 2 1 ≤ ≤ 1 pˆc pc − pˆc. (32) 1 + α j j 1 α j − − ∧ Combining (31) and (32), we have that with probability at least 1 2(n + n ) exp( 2(α min ∈ pr 1 2 i [n1] i min ∈ pc)2m) that: j [n2] j 1 ≤ ≤ 1 pˆ p − pˆ. (33) (1 + α)2 (1 α)2 ∈ For any (cid:15) (0, 1) note that if we choose: − log(2(n + n )(cid:15) 1) m = 1 ∧ 2 , (34) 2(α min ∈ pr min ∈ pc)2 i [n1] i j [n2] j − then (33) holds with probability at least 1 (cid:15) and the proof is complete. 8 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: We

text: may

text: repeat

text: the

text: analysis

text: for

text: the

text: column

text: case,

text: where

text: we

text: choose

text: t

text: α

text: min

text: pc,

text: then

text: analogously:

text: j

text: j

text: Pr[

text: pˆc

text: pc

text: α

text: min

text: pc]

text: exp(

text: min

text: j

text: j

text: j

text: j

text: j

text: j

text: For

text: any

text: i

text: [n

text: let

text: Er

text: denote

text: the

text: event

text: that

text: pˆr

text: pr

text: α

text: min

text: pr

text: and

text: for

text: any

text: j

text: [n

text: let

text: Ec

text: denote

text: 1−

text: ≥i

text: i

text: i

text: i

text: i

text: j

text: the

text: event

text: that

text: pˆc

text: pc

text: α

text: min

text: pc.

text: By

text: and

text: the

text: Union

text: Bound

text: we

text: have

text: that:

text: j

text: j

text: j

text: j

text: Pr

text: For

text: some

text: (i,

text: j)

text: the

text: event

text: Er

text: or

text: Ec

text: occurs

text: n

text: exp(

text: min

text: n

text: exp(

text: min

text: i

text: j

text: i

text: j

text: −i

text: j

text: n

text: exp(

text: min

text: pr

text: min

text: i

text: j

text: i

text: j

text: Observe

text: that

text: immediately

text: yields

text: that

text: with

text: probability

text: at

text: least

text: +n

text: exp(

text: min

text: pr

text: i

text: i

text: min

text: for

text: any

text: (i,

text: j)

text: [n

text: [n

text: we

text: have

text: that

text: the

text: two

text: following

text: bounds

text: hold:

text: j

text: j

text: pˆr

text: pr

text: α

text: min

text: pr,

text: i

text: i

text: i

text: i

text: pˆc

text: pc

text: α

text: min

text: pc.

text: j

text: j

text: j

text: j

text: The

text: bound

text: is

text: equivalent

text: to

text: the

text: following:

text: α

text: min

text: pr

text: pˆr

text: pr

text: α

text: min

text: pr,

text: i

text: i

text: i

text: i

text: i

text: i

text: and

text: the

text: above

text: inequality

text: yields

text: that

text: for

text: any

text: i

text: [n

text: pˆr

text: pr

text: pˆr.

text: α

text: i

text: i

text: α

text: i

text: Similarly

text: implies

text: that

text: for

text: any

text: j

text: [n

text: pˆc

text: pc

text: pˆc.

text: α

text: j

text: j

text: α

text: j

text: Combining

text: and

text: we

text: have

text: that

text: with

text: probability

text: at

text: least

text: n

text: exp(

text: min

text: pr

text: i

text: i

text: min

text: that:

text: j

text: j

text: pˆ

text: p

text: pˆ.

text: For

text: any

text: note

text: that

text: if

text: we

text: choose:

text: n

text: m

text: min

text: pr

text: min

text: i

text: i

text: j

text: j

text: then

text: holds

text: with

text: probability

text: at

text: least

text: and

text: the

text: proof

text: is

text: complete.

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: ACCAMS Additive Co-Clustering to Approximate Matrices Succinctly Alex Beutel Computer Science, CMU, Pittsburgh, PA, abeutel@cs.cmu.edu Amr Ahmed Google Strategic Technologies, Mountain View, CA, amra@google.com Alexander J. Smola Machine Learning, CMU, Pittsburgh, PA, alex@smola.org Google Strategic Technologies, Mountain View CA, USA May 27, 2020 Abstract Matrix completion and approximation are popular tools to capture a user’s preferences for recommendation and to approximate missing data. Instead of using low-rank factorization we take a drastically diﬀerent approach, based on the simple insight that an additive model of co-clusterings allows one to approximate matrices eﬃciently. This allows us to build a concise model that, per bit of model learned, signiﬁcantly beats all factorization approaches to matrix approximation. Even more surprisingly, we ﬁnd that summing over small co-clusterings is more eﬀective in modeling matrices than classic co-clustering, which uses just one large partitioning of the matrix. Following Occam’s razor principle suggests that the simple structure induced by our model better captures the latent preferences and decision making processes present in the real world than classic co-clustering or matrix factorization. We provide an iterative minimization algo- rithm, a collapsed Gibbs sampler, theoretical guarantees for matrix approximation, and excellent empirical evidence for the eﬃcacy of our approach. We achieve state-of-the-art results on the Netﬂix problem with a fraction of the model complexity. 1 Introduction Given users’ ratings of movies or products, how can we model a user’s preferences for diﬀerent types of items and recommend other items that the user will like? This problem, often referred to as the Netﬂix problem, has generated a ﬂurry of research in collaborative ﬁltering, with a variety of proposed matrix factorization models and inference methods. Top recommendation systems have used thousands of factors per item and per user, as was the case in the winning submissions in the Netﬂix prize [11]. Recent state-of-the-art methods have relied on learning even larger, more complex factorization models, often taking nontrivial combinations of multiple submodels [17, 14]. Such complex models use large amounts of memory, are increasingly diﬃcult to interpret, and are often diﬃcult integrate into larger systems. 1.1 Linear combinations of attributes 1

text: ACCAMS

label: title

text: Additive

text: Co-Clustering

text: to

text: Approximate

text: Matrices

text: Succinctly

text: Alex

label: author

text: Beutel

text: Computer

text: Science,

text: CMU,

text: Pittsburgh,

text: PA,

text: abeutel@cs.cmu.edu

text: Amr

text: Ahmed

text: Google

text: Strategic

text: Technologies,

text: Mountain

text: View,

text: CA,

text: amra@google.com

text: Alexander

text: J.

text: Smola

text: Machine

text: Learning,

text: CMU,

text: Pittsburgh,

text: PA,

text: alex@smola.org

text: Google

text: Strategic

text: Technologies,

text: Mountain

text: View

text: CA,

text: USA

text: May

text: Abstract

text: Matrix

label: abstract

text: completion

text: and

text: approximation

text: are

text: popular

text: tools

text: to

text: capture

text: a

text: user’s

text: preferences

text: for

text: recommendation

text: and

text: to

text: approximate

text: missing

text: data.

text: Instead

text: of

text: using

text: low-rank

text: factorization

text: we

text: take

text: a

text: drastically

text: diﬀerent

text: approach,

text: based

text: on

text: the

text: simple

text: insight

text: that

text: an

text: additive

text: model

text: of

text: co-clusterings

text: allows

text: one

text: to

text: approximate

text: matrices

text: eﬃciently.

text: This

text: allows

text: us

text: to

text: build

text: a

text: concise

text: model

text: that,

text: per

text: bit

text: of

text: model

text: learned,

text: signiﬁcantly

text: beats

text: all

text: factorization

text: approaches

text: to

text: matrix

text: approximation.

text: Even

text: more

text: surprisingly,

text: we

text: ﬁnd

text: that

text: summing

text: over

text: small

text: co-clusterings

text: is

text: more

text: eﬀective

text: in

text: modeling

text: matrices

text: than

text: classic

text: co-clustering,

text: which

text: uses

text: just

text: one

text: large

text: partitioning

text: of

text: the

text: matrix.

text: Following

text: Occam’s

text: razor

text: principle

text: suggests

text: that

text: the

text: simple

text: structure

text: induced

text: by

text: our

text: model

text: better

text: captures

text: the

text: latent

text: preferences

text: and

text: decision

text: making

text: processes

text: present

text: in

text: the

text: real

text: world

text: than

text: classic

text: co-clustering

text: or

text: matrix

text: factorization.

text: We

text: provide

text: an

text: iterative

text: minimization

text: algo-

text: rithm,

text: a

text: collapsed

text: Gibbs

text: sampler,

text: theoretical

text: guarantees

text: for

text: matrix

text: approximation,

text: and

text: excellent

text: empirical

text: evidence

text: for

text: the

text: eﬃcacy

text: of

text: our

text: approach.

text: We

text: achieve

text: state-of-the-art

text: results

text: on

text: the

text: Netﬂix

text: problem

text: with

text: a

text: fraction

text: of

text: the

text: model

text: complexity.

text: Introduction

text: Given

text: users’

text: ratings

text: of

text: movies

text: or

text: products,

text: how

text: can

text: we

text: model

text: a

text: user’s

text: preferences

text: for

text: diﬀerent

text: types

text: of

text: items

text: and

text: recommend

text: other

text: items

text: that

text: the

text: user

text: will

text: like?

text: This

text: problem,

text: often

text: referred

text: to

text: as

text: the

text: Netﬂix

text: problem,

text: has

text: generated

text: a

text: ﬂurry

text: of

text: research

text: in

text: collaborative

text: ﬁltering,

text: with

text: a

text: variety

text: of

text: proposed

text: matrix

text: factorization

text: models

text: and

text: inference

text: methods.

text: Top

text: recommendation

text: systems

text: have

text: used

text: thousands

text: of

text: factors

text: per

text: item

text: and

text: per

text: user,

text: as

text: was

text: the

text: case

text: in

text: the

text: winning

text: submissions

text: in

text: the

text: Netﬂix

text: prize

text: Recent

text: state-of-the-art

text: methods

text: have

text: relied

text: on

text: learning

text: even

text: larger,

text: more

text: complex

text: factorization

text: models,

text: often

text: taking

text: nontrivial

text: combinations

text: of

text: multiple

text: submodels

text: Such

text: complex

text: models

text: use

text: large

text: amounts

text: of

text: memory,

text: are

text: increasingly

text: diﬃcult

text: to

text: interpret,

text: and

text: are

text: often

text: diﬃcult

text: integrate

text: into

text: larger

text: systems.

text: Linear

text: combinations

text: of

text: attributes


text: )ESMR( rorre noitadnemmoceR 0.94 SVD++ 0.92 LLORMA bACCAMS 0.9 0.88 0.86 0.84 0.82 Better 0.8 0 10 20 30 40 50 60 70 80 Parameter Space Size (megabytes) Figure 1: Accuracy of ACCAMS on Netﬂix, compared to [11] and [14]. Note that our model achieves state of the art accuracy at a fraction of the model size. Our approach is drastically diﬀerent from previous collaborative ﬁltering research. Rather than start with the assumptions of a matrix factorization model, we make co-clustering eﬀective for high quality matrix completion and approximation. Co-clustering has been well studied [2, 23] but was not previously competitive in large behavior modeling and matrix completion problems. To achieve state of the art results, we use an additive model of simple co-clusterings that we call stencils, rather than building a large single co-clustering. The result is a model that is conceptually simple, has a small parameter space, has interpretable structure, and achieves the best published accuracy for matrix completion on Netﬂix, as seen in Figure 1. Using a linear combination of co-clusterings corresponds to a rather diﬀerent interpretation of user preferences and movie properties. Matrix factorization assumes that a movie preference is based on a weighted sum of preferences for diﬀerent genres, with the movie properties being represented in vectorial form. For instance, if a user likes comedies but not romantic movies, then a romantic comedy may have a predicted neutral 3-star rating. Co-clustering on the other hand assumes there exists some “correct” partitioning of movies (and users). For instance, a user might be part of a group that likes all comedies but does not like romantic movies. Correspondingly, all romantic comedies might be aggregated into a cluster, possibly partitioned further into PG-13 rated, or R-rated romantic comedies. This quickly leads to a combinatorial explosion. By taking a linear combination of co-clusterings we beneﬁt from both perspectives: there is no single correct partitioning of movies and users; however, we can use the membership in several independent groups to encode the factorial nature of attributes without incurring the cost of a { necessarily high-dimensional model of matrix factorization. For instance, a movie may be funny, } { sad, thoughtful , it might have a certain age rating, it might be an action, romantic, thriller, } documentary, family movie, it might be shot in a certain visual style, and by a certain group of actors. By taking linear combinations of co-clusterings we can take these attributes into account. 1.2 Stencils The mathematical challenge that motivated this work is that, in order to encode a rank-k matrix by a factorization, we need k numbers per row (and column) respectively. With linear combinations 2 ##LTFigure## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: )ESMR(

font: default

text: rorre

text: noitadnemmoceR

text: SVD++

text: LLORMA

text: bACCAMS

text: Better

text: Parameter

text: Space

text: Size

text: (megabytes)

text: Figure

text: Accuracy

label: caption

text: of

text: ACCAMS

text: on

text: Netﬂix,

text: compared

text: to

text: and

text: Note

text: that

text: our

text: model

text: achieves

text: state

text: of

text: the

text: art

text: accuracy

text: at

text: a

text: fraction

text: of

text: the

text: model

text: size.

text: Our

text: approach

text: is

text: drastically

text: diﬀerent

text: from

text: previous

text: collaborative

text: ﬁltering

text: research.

text: Rather

text: than

text: start

text: with

text: the

text: assumptions

text: of

text: a

text: matrix

text: factorization

text: model,

text: we

text: make

text: co-clustering

text: eﬀective

text: for

text: high

text: quality

text: matrix

text: completion

text: and

text: approximation.

text: Co-clustering

text: has

text: been

text: well

text: studied

text: but

text: was

text: not

text: previously

text: competitive

text: in

text: large

text: behavior

text: modeling

text: and

text: matrix

text: completion

text: problems.

text: To

text: achieve

text: state

text: of

text: the

text: art

text: results,

text: we

text: use

text: an

text: additive

text: model

text: of

text: simple

text: co-clusterings

text: that

text: we

text: call

text: stencils,

text: rather

text: than

text: building

text: a

text: large

text: single

text: co-clustering.

text: The

text: result

text: is

text: a

text: model

text: that

text: is

text: conceptually

text: simple,

text: has

text: a

text: small

text: parameter

text: space,

text: has

text: interpretable

text: structure,

text: and

text: achieves

text: the

text: best

text: published

text: accuracy

text: for

text: matrix

text: completion

text: on

text: Netﬂix,

text: as

text: seen

text: in

text: Figure

text: Using

text: a

text: linear

text: combination

text: of

text: co-clusterings

text: corresponds

text: to

text: a

text: rather

text: diﬀerent

text: interpretation

text: of

text: user

text: preferences

text: and

text: movie

text: properties.

text: Matrix

text: factorization

text: assumes

text: that

text: a

text: movie

text: preference

text: is

text: based

text: on

text: a

text: weighted

text: sum

text: of

text: preferences

text: for

text: diﬀerent

text: genres,

text: with

text: the

text: movie

text: properties

text: being

text: represented

text: in

text: vectorial

text: form.

text: For

text: instance,

text: if

text: a

text: user

text: likes

text: comedies

text: but

text: not

text: romantic

text: movies,

text: then

text: a

text: romantic

text: comedy

text: may

text: have

text: a

text: predicted

text: neutral

text: rating.

text: Co-clustering

text: on

text: the

text: other

text: hand

text: assumes

text: there

text: exists

text: some

text: “correct”

text: partitioning

text: of

text: movies

text: (and

text: users).

text: For

text: instance,

text: a

text: user

text: might

text: be

text: part

text: of

text: a

text: group

text: that

text: likes

text: all

text: comedies

text: but

text: does

text: not

text: like

text: romantic

text: movies.

text: Correspondingly,

text: all

text: romantic

text: comedies

text: might

text: be

text: aggregated

text: into

text: a

text: cluster,

text: possibly

text: partitioned

text: further

text: into

text: rated,

text: or

text: R-rated

text: romantic

text: comedies.

text: This

text: quickly

text: leads

text: to

text: a

text: combinatorial

text: explosion.

text: By

text: taking

text: a

text: linear

text: combination

text: of

text: co-clusterings

text: we

text: beneﬁt

text: from

text: both

text: perspectives:

text: there

text: is

text: no

text: single

text: correct

text: partitioning

text: of

text: movies

text: and

text: users;

text: however,

text: we

text: can

text: use

text: the

text: membership

text: in

text: several

text: independent

text: groups

text: to

text: encode

text: the

text: factorial

text: nature

text: of

text: attributes

text: without

text: incurring

text: the

text: cost

text: of

text: a

text: necessarily

text: high-dimensional

text: model

text: of

text: matrix

text: factorization.

text: For

text: instance,

text: a

text: movie

text: may

text: be

text: funny,

text: sad,

text: thoughtful

text: it

text: might

text: have

text: a

text: certain

text: age

text: rating,

text: it

text: might

text: be

text: an

text: action,

text: romantic,

text: thriller,

text: documentary,

text: family

text: movie,

text: it

text: might

text: be

text: shot

text: in

text: a

text: certain

text: visual

text: style,

text: and

text: by

text: a

text: certain

text: group

text: of

text: actors.

text: By

text: taking

text: linear

text: combinations

text: of

text: co-clusterings

text: we

text: can

text: take

text: these

text: attributes

text: into

text: account.

text: Stencils

text: The

text: mathematical

text: challenge

text: that

text: motivated

text: this

text: work

text: is

text: that,

text: in

text: order

text: to

text: encode

text: a

text: rank-k

text: matrix

text: by

text: a

text: factorization,

text: we

text: need

text: k

text: numbers

text: per

text: row

text: (and

text: column)

text: respectively.

text: With

text: linear

text: combinations

text: ##LTFigure##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: of stencils, on the other hand, we only need log k bits per row (and column) plus O(k2) ﬂoating 2 point numbers regardless of the size of the matrix. × We denote by a stencil a small k k template of a matrix and its mapping to the row and column vectors respectively. This is best understood by the example below: assume that we have × × two simple stencils containing 3 3 and 3 2 co-clusterings. Their linear combination yields a × rather nontrivial 9 9 matrix of rank 5. + = · × · In contrast, classic co-clustering would require a (3 3) (3 2) partitioning to match this structure. × × When we have s stencils of size k k, this requires a ks ks partitioning. By design our model has a parameter space that is an order of magnitude smaller than competing methods, requiring only s log k bits per user and per movie and sk2 ﬂoating point numbers, where 2 k is generally quite small. This is computationally advantageous of course, but also demonstrates that our modeling assumptions better match real world structure of human decision making. Finding succinct models for binary matrices, e.g. by minimizing the minimum description (MDL), has been the focus of signiﬁcant research and valuable results in the data mining com- munity [15, 12]. That said, these models are quite diﬀerent. To the best of our knowledge, ours is the ﬁrst work aimed at ﬁnding a parsimonious model for general (real-valued) matrix completion and approximation. 1.3 Contributions Our paper makes a number of contributions to the problem of ﬁnding sparse representations of matrices. • We present ACCAMS, an iterative k-means style algorithm that minimizes the approximation error by backﬁtting the residuals of previous approximations. • We provide linear approximation rates exploiting the geometry of rows and columns of rating matrix via bounds on the metric entropy of Banach spaces. • We present a generative Bayesian non-parametric model and devise a collapsed Gibbs sam- pling algorithm, bACCAMS, for eﬃcient inference. • Experiments conﬁrm the eﬃcacy of our approach, oﬀering the best published results for matrix completion on Netﬂix, an interpretable hierarchy of content, and succinct matrix approximations for ratings, image, and network data. We believe that these contributions oﬀer a promising new direction for behavior modeling and matrix approximation. 3 ##LTFigure##

text: of

text: stencils,

text: on

text: the

text: other

text: hand,

text: we

text: only

text: need

text: log

text: k

text: bits

text: per

text: row

text: (and

text: column)

text: plus

text: ﬂoating

text: point

text: numbers

text: regardless

text: of

text: the

text: size

text: of

text: the

text: matrix.

text: We

text: denote

text: by

text: a

text: stencil

text: a

text: small

text: k

text: k

text: template

text: of

text: a

text: matrix

text: and

text: its

text: mapping

text: to

text: the

text: row

text: and

text: column

text: vectors

text: respectively.

text: This

text: is

text: best

text: understood

text: by

text: the

text: example

text: below:

text: assume

text: that

text: we

text: have

text: two

text: simple

text: stencils

text: containing

text: and

text: co-clusterings.

text: Their

text: linear

text: combination

text: yields

text: a

text: rather

text: nontrivial

text: matrix

text: of

text: rank

text: In

text: contrast,

text: classic

text: co-clustering

text: would

text: require

text: a

text: partitioning

text: to

text: match

text: this

text: structure.

text: When

text: we

text: have

text: s

text: stencils

text: of

text: size

text: k

text: k,

text: this

text: requires

text: a

text: ks

text: ks

text: partitioning.

text: By

text: design

text: our

text: model

text: has

text: a

text: parameter

text: space

text: that

text: is

text: an

text: order

text: of

text: magnitude

text: smaller

text: than

text: competing

text: methods,

text: requiring

text: only

text: s

text: log

text: k

text: bits

text: per

text: user

text: and

text: per

text: movie

text: and

text: ﬂoating

text: point

text: numbers,

text: where

text: k

text: is

text: generally

text: quite

text: small.

text: This

text: is

text: computationally

text: advantageous

text: of

text: course,

text: but

text: also

text: demonstrates

text: that

text: our

text: modeling

text: assumptions

text: better

text: match

text: real

text: world

text: structure

text: of

text: human

text: decision

text: making.

text: Finding

text: succinct

text: models

text: for

text: binary

text: matrices,

text: e.g.

text: by

text: minimizing

text: the

text: minimum

text: description

text: (MDL),

text: has

text: been

text: the

text: focus

text: of

text: signiﬁcant

text: research

text: and

text: valuable

text: results

text: in

text: the

text: data

text: mining

text: com-

text: munity

text: That

text: said,

text: these

text: models

text: are

text: quite

text: diﬀerent.

text: To

text: the

text: best

text: of

text: our

text: knowledge,

text: ours

text: is

text: the

text: ﬁrst

text: work

text: aimed

text: at

text: ﬁnding

text: a

text: parsimonious

text: model

text: for

text: general

text: (real-valued)

text: matrix

text: completion

text: and

text: approximation.

text: Contributions

text: Our

text: paper

text: makes

text: a

text: number

text: of

text: contributions

text: to

text: the

text: problem

text: of

text: ﬁnding

text: sparse

text: representations

text: of

text: matrices.

text: We

text: present

text: ACCAMS,

text: an

text: iterative

text: k-means

text: style

text: algorithm

text: that

text: minimizes

text: the

text: approximation

text: error

text: by

text: backﬁtting

text: the

text: residuals

text: of

text: previous

text: approximations.

text: We

text: provide

text: linear

text: approximation

text: rates

text: exploiting

text: the

text: geometry

text: of

text: rows

text: and

text: columns

text: of

text: rating

text: matrix

text: via

text: bounds

text: on

text: the

text: metric

text: entropy

text: of

text: Banach

text: spaces.

text: We

text: present

text: a

text: generative

text: Bayesian

text: non-parametric

text: model

text: and

text: devise

text: a

text: collapsed

text: Gibbs

text: sam-

text: pling

text: algorithm,

text: bACCAMS,

text: for

text: eﬃcient

text: inference.

text: Experiments

text: conﬁrm

text: the

text: eﬃcacy

text: of

text: our

text: approach,

text: oﬀering

text: the

text: best

text: published

text: results

text: for

text: matrix

text: completion

text: on

text: Netﬂix,

text: an

text: interpretable

text: hierarchy

text: of

text: content,

text: and

text: succinct

text: matrix

text: approximations

text: for

text: ratings,

text: image,

text: and

text: network

text: data.

text: We

text: believe

text: that

text: these

text: contributions

text: oﬀer

text: a

text: promising

text: new

text: direction

text: for

text: behavior

text: modeling

text: and

text: matrix

text: approximation.

text: ##LTFigure##


text: often directly optimizing the model size described by the minimum description language (MDL) principle [22]. Finding eﬀective ways to compress real world data allows for better modeling and understanding of the datasets. This approach has led to valuable results in pattern and item-set mining [26, 15] as well as graph summarization [12]. However, these approaches typically focus on modeling databases of discrete items rather than real-valued datasets with missing values. 3 Matrix Approximation Before delving into the details of Bayesian Non-parametrics we begin with an optimization view of ACCAMS. 3.1 Model Key to our model is the notion of a stencil, an extremely easy to represent block-wise constant rank-k matrix. ∈ R × Deﬁnition 1 (Stencil) A stencil S(T, c, d) is a matrix S m n with the property that S = ∈ R × ∈ { } ∈ { ij } Tci,dj for a template T km kn and discrete index vectors c 1, . . . , km m and d 1, . . . , kn n respectively. ∈ R × Given a matrix M m n it is now our goal to ﬁnd a stencil S(T, c, d) such that the approximation − error M S(T, c, d) is small while simultaneously the cost for storing T, c, d is small. In the context × × of the example above, the 9 9 matrix is given by the sum of two stencils, one of size 3 3 and × one of size 3 2. This already indicates that we may require more than one stencil for eﬃcient approximation. In general, our model will be such as to solve (cid:13) (cid:13) (cid:13) (cid:88) (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) s 2 − m{inimiz}e M S(T l, cl, dl) (1) Tl,cl,dl l=1 Frob That is, we would like to ﬁnd an additive model of s stencils that minimizes the approximation error to M. Such an expansion aﬀords eﬃcient compression using a trivial codebook, as can be seen below. Lemma 2 (Compression) The stencil S(T, c, d) can be stored at (cid:15) element-wise accuracy at no more cost than − (cid:107) (cid:107) O(m log k + n log k + k k log (cid:15) 1 T ∞). 2 m 2 n m n 2 Proof This follows directly from the construction. Storing the vector c costs at most m log k 2 m bits if we assume a uniform code (this also holds for d). When storing T approximately, we must not quantize at a level of the approximation error or higher. Hence, a simplistic means of encoding (cid:107) (cid:107) the dynamic range requires log T ∞ /(cid:15) bit, which is used on a per-element basis in T . 2 Note that considerably better codes may exist whenever the entropy of c is less than log k 2 m (likewise for d). Nonetheless, even the crude log k bound is already much better than what can 2 m be accomplished by a low-rank factorization. Obviously, given M, it is our goal to ﬁnd such stencils S(T, c, d) with good approximation properties. Unfortunately, ﬁnding linear combinations of co-clusterings is as hard as co-clustering: assume that we are given all but one stencil of the optimal solution. In this case our problem reduces to co-clustering as its subproblem, which is NP-hard. 5

text: often

text: directly

text: optimizing

text: the

text: model

text: size

text: described

text: by

text: the

text: minimum

text: description

text: language

text: (MDL)

text: principle

text: Finding

text: eﬀective

text: ways

text: to

text: compress

text: real

text: world

text: data

text: allows

text: for

text: better

text: modeling

text: and

text: understanding

text: of

text: the

text: datasets.

text: This

text: approach

text: has

text: led

text: to

text: valuable

text: results

text: in

text: pattern

text: and

text: item-set

text: mining

text: as

text: well

text: as

text: graph

text: summarization

text: However,

text: these

text: approaches

text: typically

text: focus

text: on

text: modeling

text: databases

text: of

text: discrete

text: items

text: rather

text: than

text: real-valued

text: datasets

text: with

text: missing

text: values.

label: section

text: Matrix

text: Approximation

text: Before

text: delving

text: into

text: the

text: details

text: of

text: Bayesian

text: Non-parametrics

text: we

text: begin

text: with

text: an

text: optimization

text: view

text: of

text: ACCAMS.

text: Model

text: Key

text: to

text: our

text: model

text: is

text: the

text: notion

text: of

text: a

text: stencil,

text: an

text: extremely

text: easy

text: to

text: represent

text: block-wise

text: constant

text: rank-k

text: matrix.

text: R

text: Deﬁnition

text: (Stencil)

text: A

text: stencil

text: S(T,

text: c,

text: d)

text: is

text: a

text: matrix

text: S

text: m

text: n

text: with

text: the

text: property

text: that

text: S

text: R

text: ij

text: Tci,dj

text: for

text: a

text: template

text: T

text: km

text: kn

text: and

text: discrete

text: index

text: vectors

text: c

text: km

text: m

text: and

text: d

text: kn

text: n

text: respectively.

text: R

text: Given

text: a

text: matrix

text: M

text: m

text: n

text: it

text: is

text: now

text: our

text: goal

text: to

text: ﬁnd

text: a

text: stencil

text: S(T,

text: c,

text: d)

text: such

text: that

text: the

text: approximation

text: error

text: M

text: S(T,

text: c,

text: d)

text: is

text: small

text: while

text: simultaneously

text: the

text: cost

text: for

text: storing

text: T,

text: c,

text: d

text: is

text: small.

text: In

text: the

text: context

text: of

text: the

text: example

text: above,

text: the

text: matrix

text: is

text: given

text: by

text: the

text: sum

text: of

text: two

text: stencils,

text: one

text: of

text: size

text: and

text: one

text: of

text: size

text: This

text: already

text: indicates

text: that

text: we

text: may

text: require

text: more

text: than

text: one

text: stencil

text: for

text: eﬃcient

text: approximation.

text: In

text: general,

text: our

text: model

text: will

text: be

text: such

text: as

text: to

text: solve

text: s

text: m{inimiz}e

text: M

text: S(T

text: l,

text: cl,

text: dl)

text: Tl,cl,dl

text: Frob

text: That

text: is,

text: we

text: would

text: like

text: to

text: ﬁnd

text: an

text: additive

text: model

text: of

text: s

text: stencils

text: that

text: minimizes

text: the

text: approximation

text: error

text: to

text: M.

text: Such

text: an

text: expansion

text: aﬀords

text: eﬃcient

text: compression

text: using

text: a

text: trivial

text: codebook,

text: as

text: can

text: be

text: seen

text: below.

text: Lemma

text: (Compression)

text: The

text: stencil

text: S(T,

text: c,

text: d)

text: can

text: be

text: stored

text: at

text: element-wise

text: accuracy

text: at

text: no

text: more

text: cost

text: than

text: O(m

text: log

text: k

text: n

text: log

text: k

text: k

text: k

text: log

text: T

text: m

text: n

text: m

text: n

text: Proof

text: This

text: follows

text: directly

text: from

text: the

text: construction.

text: Storing

text: the

text: vector

text: c

text: costs

text: at

text: most

text: m

text: log

text: k

text: m

text: bits

text: if

text: we

text: assume

text: a

text: uniform

text: code

text: (this

text: also

text: holds

text: for

text: d).

text: When

text: storing

text: T

text: approximately,

text: we

text: must

text: not

text: quantize

text: at

text: a

text: level

text: of

text: the

text: approximation

text: error

text: or

text: higher.

text: Hence,

text: a

text: simplistic

text: means

text: of

text: encoding

text: the

text: dynamic

text: range

text: requires

text: log

text: T

text: bit,

text: which

text: is

text: used

text: on

text: a

text: per-element

text: basis

text: in

text: T

text: Note

text: that

text: considerably

text: better

text: codes

text: may

text: exist

text: whenever

text: the

text: entropy

text: of

text: c

text: is

text: less

text: than

text: log

text: k

text: m

text: (likewise

text: for

text: d).

text: Nonetheless,

text: even

text: the

text: crude

text: log

text: k

text: bound

text: is

text: already

text: much

text: better

text: than

text: what

text: can

text: m

text: be

text: accomplished

text: by

text: a

text: low-rank

text: factorization.

text: Obviously,

text: given

text: M,

text: it

text: is

text: our

text: goal

text: to

text: ﬁnd

text: such

text: stencils

text: S(T,

text: c,

text: d)

text: with

text: good

text: approximation

text: properties.

text: Unfortunately,

text: ﬁnding

text: linear

text: combinations

text: of

text: co-clusterings

text: is

text: as

text: hard

text: as

text: co-clustering:

text: assume

text: that

text: we

text: are

text: given

text: all

text: but

text: one

text: stencil

text: of

text: the

text: optimal

text: solution.

text: In

text: this

text: case

text: our

text: problem

text: reduces

text: to

text: co-clustering

text: as

text: its

text: subproblem,

text: which

text: is

text: NP-hard.


text: (cid:12) (cid:10) (cid:11)(cid:12) (cid:12) (cid:10) (cid:11)(cid:12) (cid:12) (cid:12) (cid:12) (cid:48) (cid:12) holds for the matrix R, as approximated by R . Hence we have (cid:12)(cid:10) (cid:11) (cid:10) (cid:11)(cid:12) − (cid:48) (cid:48) (cid:12)(cid:104) (cid:105) − (cid:48) (cid:48) (cid:12) M Q , R = (cid:13) Q , R (cid:13) Q , R (cid:13) (cid:13) (cid:13) (cid:13) ij i: j: (cid:13) i: −j: (cid:48)(cid:13) i: j(cid:13): (cid:48) (cid:13) (cid:13)− (cid:48) (cid:13) = Qi: Qi(cid:16):, Rj:(cid:17) + Qi:, Rj: Rj: ≤ − (cid:48) (cid:107) (cid:107) (cid:48) − (cid:48) Q Q R + Q R R i: i: j: i: j: j: ≤ (cid:107) (cid:107) 1 1 2 M 2 (cid:15)l Σ2 This provides a pointwise approximation guarantee.If we only have a bound on the rank and on (cid:107) (cid:107) M , this yields | − (cid:104) (cid:105)| ≤ (cid:107) (cid:107) 1 Mij qi, rj 12 M l2d Moreover, since each row in Q√and R respectively wi√ll be approximated with residual bounded by (cid:107) − (cid:48)(cid:107) ≤ (cid:107) − (cid:48)(cid:107) ≤ (cid:15) we can bound Q Q(cid:13)(cid:2) m(cid:15) a(cid:3)nd(cid:13) R(cid:13) R n(cid:15)(cid:13) res(cid:13)pectively. Th(cid:13)is yields a bound on the l (cid:13) l (cid:13) (cid:13) (cid:13)l (cid:13) (cid:13) matrix norm of the residual via (cid:16) (cid:17) − (cid:48) (cid:48) ≤ − (cid:48) − (cid:48) (cid:48) QR Q R x Q(R R )x + (Q Q )R x √ √ ≤ (cid:107) (cid:107) (cid:107) (cid:107) 1 1 ( m + n) M 2 (cid:15)l Σ2 x This bounds the matrix norm of the residual. Note that the above is an existence proof rather than a constructive prescription. However, by using the fact that set cover is a submodular problem [28], it follows that given l, we are able to obtain a near-optimal cover, thus leading to a constructive algorithm. Note, however, that the main purpose of the above analysis is to obtain theoretical upper bounds on the rate of convergence. In practice, the results can be considerably better, as we show in Section . 4 Generative Model In the same manner as many risk minimization problems (e.g. penalized logistic regression) have a Bayesian counterpart (Gaussian Process classiﬁcation) [18], we now devise a Bayesian coun- terpart to ACCAMS, which we will refer to as bACCAMS. We begin with the single stencil case in Section and extend it to many stencils in Section . 4.1 Co-Clustering with a Single Stencil We begin with a simplistic model of co-clustering. It serves as the basic template for single- matrix inference. All subsequent steps use the same idea. In a nutshell, we assume that each user u belongs to a particular cluster c drawn from a Chinese Restaurant Process CRP(α). Likewise, u we assume that each movie m belongs to some cluster d drawn analogously from CRP(β). The m ∼ scores of the matrix M are obtained from a stencil S(T, c, d) = T with additive noise (cid:15) N um um cudm N um (0, σ2). The stencil values T themselves are drawn from a normal distribution (0, τ2). In turn, cd the variances τ2 and σ2 are obtained via a conjugate prior, i.e. the Inverse Gamma distribution. This is an extremely simple model similar to [23], akin to a decision stump. The rationale for picking such a primitive model is that we will be combining linear combinations thereof to obtain a very ﬂexible tool. The model is shown in Figure 2. For l = 1 the formal deﬁnition is as follows: (cid:0) (cid:1) ∼ ∼ c CRP(α) d CRP(β) (7a) u m ∼ N ∼ N T (0, τ2) M T , σ2 (7b) cd ∼ um ∼ cudm τ2 IG(γ) σ2 IG(η) (7c) 9 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: holds

text: for

text: the

text: matrix

text: R,

text: as

text: approximated

text: by

text: R

text: Hence

text: we

text: have

text: M

text: Q

text: R

text: Q

text: R

text: Q

text: R

text: ij

text: i:

text: j:

text: i:

text: −j:

text: i:

text: Qi:

text: Qi:,

text: Rj:

text: Rj:

text: Q

text: Q

text: R

text: Q

text: R

text: R

text: i:

text: i:

text: j:

text: i:

text: j:

text: j:

text: M

text: Σ2

text: This

text: provides

text: a

text: pointwise

text: approximation

text: guarantee.If

text: we

text: only

text: have

text: a

text: bound

text: on

text: the

text: rank

text: and

text: on

text: M

text: this

text: yields

text: Mij

text: qi,

text: rj

text: M

text: Moreover,

text: since

text: each

text: row

text: in

text: Q√and

text: R

text: respectively

text: wi√ll

text: be

text: approximated

text: with

text: residual

text: bounded

text: by

text: we

text: can

text: bound

text: Q

text: R

text: yields

text: a

text: bound

text: on

text: the

text: l

text: l

text: matrix

text: norm

text: of

text: the

text: residual

text: via

text: QR

text: Q

text: R

text: x

text: Q(R

text: R

text: )x

text: (Q

text: Q

text: )R

text: x

text: m

text: n)

text: M

text: Σ2

text: x

text: This

text: bounds

text: the

text: matrix

text: norm

text: of

text: the

text: residual.

text: Note

text: that

text: the

text: above

text: is

text: an

text: existence

text: proof

text: rather

text: than

text: a

text: constructive

text: prescription.

text: However,

text: by

text: using

text: the

text: fact

text: that

text: set

text: cover

text: is

text: a

text: submodular

text: problem

text: it

text: follows

text: that

text: given

text: l,

text: we

text: are

text: able

text: to

text: obtain

text: a

text: near-optimal

text: cover,

text: thus

text: leading

text: to

text: a

text: constructive

text: algorithm.

text: Note,

text: however,

text: that

text: the

text: main

text: purpose

text: of

text: the

text: above

text: analysis

text: is

text: to

text: obtain

text: theoretical

text: upper

text: bounds

text: on

text: the

text: rate

text: of

text: convergence.

text: In

text: practice,

text: the

text: results

text: can

text: be

text: considerably

text: better,

text: as

text: we

text: show

text: in

text: Section

text: Generative

text: Model

text: In

text: the

text: same

text: manner

text: as

text: many

text: risk

text: minimization

text: problems

text: (e.g.

text: penalized

text: logistic

text: regression)

text: have

text: a

text: Bayesian

text: counterpart

text: (Gaussian

text: Process

text: classiﬁcation)

text: we

text: now

text: devise

text: a

text: Bayesian

text: coun-

text: terpart

text: to

text: ACCAMS,

text: which

text: we

text: will

text: refer

text: to

text: as

text: bACCAMS.

text: We

text: begin

text: with

text: the

text: single

text: stencil

text: case

text: in

text: Section

text: and

text: extend

text: it

text: to

text: many

text: stencils

text: in

text: Section

text: Co-Clustering

text: with

text: a

text: Single

text: Stencil

text: We

text: begin

text: with

text: a

text: simplistic

text: model

text: of

text: co-clustering.

text: It

text: serves

text: as

text: the

text: basic

text: template

text: for

text: single-

text: matrix

text: inference.

text: All

text: subsequent

text: steps

text: use

text: the

text: same

text: idea.

text: In

text: a

text: nutshell,

text: we

text: assume

text: that

text: each

text: user

text: u

text: belongs

text: to

text: a

text: particular

text: cluster

text: c

text: drawn

text: from

text: a

text: Chinese

text: Restaurant

text: Process

text: CRP(α).

text: Likewise,

text: u

text: we

text: assume

text: that

text: each

text: movie

text: m

text: belongs

text: to

text: some

text: cluster

text: d

text: drawn

text: analogously

text: from

text: CRP(β).

text: The

text: m

text: scores

text: of

text: the

text: matrix

text: M

text: are

text: obtained

text: from

text: a

text: stencil

text: S(T,

text: c,

text: d)

text: T

text: with

text: additive

text: noise

text: N

text: um

text: um

text: cudm

text: N

text: um

text: The

text: stencil

text: values

text: T

text: themselves

text: are

text: drawn

text: from

text: a

text: normal

text: distribution

text: In

text: turn,

text: cd

text: the

text: variances

text: τ2

text: and

text: σ2

text: are

text: obtained

text: via

text: a

text: conjugate

text: prior,

text: i.e.

text: the

text: Inverse

text: Gamma

text: distribution.

text: This

text: is

text: an

text: extremely

text: simple

text: model

text: similar

text: to

text: akin

text: to

text: a

text: decision

text: stump.

text: The

text: rationale

text: for

text: picking

text: such

text: a

text: primitive

text: model

text: is

text: that

text: we

text: will

text: be

text: combining

text: linear

text: combinations

text: thereof

text: to

text: obtain

text: a

text: very

text: ﬂexible

text: tool.

text: The

text: model

text: is

text: shown

text: in

text: Figure

text: For

text: l

text: the

text: formal

text: deﬁnition

text: is

text: as

text: follows:

text: c

text: CRP(α)

text: d

text: CRP(β)

text: u

text: m

text: N

text: N

text: T

text: M

text: T

text: σ2

text: cd

text: um

text: cudm

text: τ2

text: IG(γ)

text: σ2

text: IG(η)

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 17 Elza Erkip Elza Erkip (S’93-M’96-SM’05-F’11) received the B.S. degree in electrical and electronics engineering from Middle East Technical University, Ankara, Turkey, and the M.S. and Ph.D. degrees in electrical engineering from Stanford University, Stanford, CA, USA. Currently, she is a Professor of electrical and computer engineering with New York University Polytechnic School of Engineering, Brooklyn, NY, USA. Her research interests are in information theory, communication theory, and wire- less communications. Dr. Erkip is a member of the Science Academy Society of Turkey and is among the Thomson Reuters 2014 Edition of Highly Cited Researchers. She received the NSF CAREER award in 2001, the IEEE Communications Society Stephen O. Rice Paper Prize in 2004, the IEEE ICC Communication Theory Symposium Best Paper Award in 2007, and the IEEE Communications Society Award for Advances in Communication in 2013. She co-authored a paper that received the IEEE International Symposium on Information Theory Student Paper Award in 2007. Currently, she is a Member of the Board of Governors of the IEEE Information Theory Society and a Guest Editor of the IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS. Dr. Erkip was a Distinguished Lecturer of the IEEE Information Theory Society from 2013 to 2014, an Associate Editor of the IEEE TRANSACTIONS ON INFORMATION THEORY from 2009 to 2011, an Associate Editor of the IEEE TRANSACTIONS ON COMMUNICATIONS from 2006 to 2008, a Publications Editor of the IEEE TRANSACTIONS ON INFOR- MATION THEORY from 2006 to 2008 and a Guest Editor of the IEEE SIGNAL PROCESSING MAGAZINE in 2007. She was a General Chair for the IEEE International Symposium of Information Theory in 2013, a Technical Program Chair for the International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOpt) in 2011, a Technical Program Chair for the IEEE GLOBECOM Communication Theory Symposium in 2009, the Publications Chair for the IEEE Information Theory Workshop, Taormina, in 2009, the Technical Area Chair for the MIMO Communications and Signal Processing track of Asilomar Conference on Signals, Systems, and Computers in 2007, and a Technical Program Chair for the IEEE Communication Theory Workshop in 2006. Mihaela Beluri Mihaela Beluri (M’90) received the M.S. degree in electrical engineering from the Polytechnic University of Bucharest, Romania. She is currently a Principal Engineer with InterDigital Communications, Melville, NY, working on mil- limeter wave technologies. Her recent experience includes dynamic spectrum management and shared spectrum technologies, algorithm design, modeling and simulations for WCDMA, HSPA and LTE sys- tems. She has authored or coauthored IEEE confer- ence publications and holds several patents. Rui Yang Rui Yang received the M.S. and Ph.D. de- grees in electrical engineering from the University of Maryland, College Park, in 1987 and 1992, respec- tively. He has 15 years of experience in the research and development of wireless communication sys- tems. Since he joined InterDigital Communications in 2000, he has led several product development and research projects. He is currently a Principle Engineer at InterDigital Labs, leading a project on baseband and RF waveforms for future wireless communication systems. His interests include digital signal processing and air interface design. He has received more than 15 patent awards in those areas. ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure##

text: Elza

text: Erkip

text: Elza

text: Erkip

text: received

text: the

text: B.S.

text: degree

text: in

text: electrical

text: and

text: electronics

text: engineering

text: from

text: Middle

text: East

text: Technical

text: University,

text: Ankara,

text: Turkey,

text: and

text: the

text: M.S.

text: and

text: Ph.D.

text: degrees

text: in

text: electrical

text: engineering

text: from

text: Stanford

text: University,

text: Stanford,

text: CA,

text: USA.

text: Currently,

text: she

text: is

text: a

text: Professor

text: of

text: electrical

text: and

text: computer

text: engineering

text: with

text: New

text: York

text: University

text: Polytechnic

text: School

text: of

text: Engineering,

text: Brooklyn,

text: NY,

text: USA.

text: Her

text: research

text: interests

text: are

text: in

text: information

text: theory,

text: communication

text: theory,

text: and

text: wire-

text: less

text: communications.

text: Dr.

text: Erkip

text: is

text: a

text: member

text: of

text: the

text: Science

text: Academy

text: Society

text: of

text: Turkey

text: and

text: is

text: among

text: the

text: Thomson

text: Reuters

text: Edition

text: of

text: Highly

text: Cited

text: Researchers.

text: She

text: received

text: the

text: NSF

text: CAREER

text: award

text: in

text: the

text: IEEE

text: Communications

text: Society

text: Stephen

text: O.

text: Rice

text: Paper

text: Prize

text: in

text: the

text: IEEE

text: ICC

text: Communication

text: Theory

text: Symposium

text: Best

text: Paper

text: Award

text: in

text: and

text: the

text: IEEE

text: Communications

text: Society

text: Award

text: for

text: Advances

text: in

text: Communication

text: in

text: She

text: co-authored

text: a

text: paper

text: that

text: received

text: the

text: IEEE

text: International

text: Symposium

text: on

text: Information

text: Theory

text: Student

text: Paper

text: Award

text: in

text: Currently,

text: she

text: is

text: a

text: Member

text: of

text: the

text: Board

text: of

text: Governors

text: of

text: the

text: IEEE

text: Information

text: Theory

text: Society

text: and

text: a

text: Guest

text: Editor

text: of

text: the

text: IEEE

text: JOURNAL

text: ON

text: SELECTED

text: AREAS

text: IN

text: COMMUNICATIONS.

text: Dr.

text: Erkip

text: was

text: a

text: Distinguished

text: Lecturer

text: of

text: the

text: IEEE

text: Information

text: Theory

text: Society

text: from

text: to

text: an

text: Associate

text: Editor

text: of

text: the

text: IEEE

text: TRANSACTIONS

text: ON

text: INFORMATION

text: THEORY

text: from

text: to

text: an

text: Associate

text: Editor

text: of

text: the

text: IEEE

text: TRANSACTIONS

text: ON

text: COMMUNICATIONS

text: from

text: to

text: a

text: Publications

text: Editor

text: of

text: the

text: IEEE

text: TRANSACTIONS

text: ON

text: INFOR-

text: MATION

text: THEORY

text: from

text: to

text: and

text: a

text: Guest

text: Editor

text: of

text: the

text: IEEE

text: SIGNAL

text: PROCESSING

text: MAGAZINE

text: in

text: She

text: was

text: a

text: General

text: Chair

text: for

text: the

text: IEEE

text: International

text: Symposium

text: of

text: Information

text: Theory

text: in

text: a

text: Technical

text: Program

text: Chair

text: for

text: the

text: International

text: Symposium

text: on

text: Modeling

text: and

text: Optimization

text: in

text: Mobile,

text: Ad

text: Hoc,

text: and

text: Wireless

text: Networks

text: (WiOpt)

text: in

text: a

text: Technical

text: Program

text: Chair

text: for

text: the

text: IEEE

text: GLOBECOM

text: Communication

text: Theory

text: Symposium

text: in

text: the

text: Publications

text: Chair

text: for

text: the

text: IEEE

text: Information

text: Theory

text: Workshop,

text: Taormina,

text: in

text: the

text: Technical

text: Area

text: Chair

text: for

text: the

text: MIMO

text: Communications

text: and

text: Signal

text: Processing

text: track

text: of

text: Asilomar

text: Conference

text: on

text: Signals,

text: Systems,

text: and

text: Computers

text: in

text: and

text: a

text: Technical

text: Program

text: Chair

text: for

text: the

text: IEEE

text: Communication

text: Theory

text: Workshop

text: in

text: Mihaela

text: Beluri

text: Mihaela

text: Beluri

text: received

text: the

text: M.S.

text: degree

text: in

text: electrical

text: engineering

text: from

text: the

text: Polytechnic

text: University

text: of

text: Bucharest,

text: Romania.

text: She

text: is

text: currently

text: a

text: Principal

text: Engineer

text: with

text: InterDigital

text: Communications,

text: Melville,

text: NY,

text: working

text: on

text: mil-

text: limeter

text: wave

text: technologies.

text: Her

text: recent

text: experience

text: includes

text: dynamic

text: spectrum

text: management

text: and

text: shared

text: spectrum

text: technologies,

text: algorithm

text: design,

text: modeling

text: and

text: simulations

text: for

text: WCDMA,

text: HSPA

text: and

text: LTE

text: sys-

text: tems.

text: She

text: has

text: authored

text: or

text: coauthored

text: IEEE

text: confer-

text: ence

text: publications

text: and

text: holds

text: several

text: patents.

text: Rui

text: Yang

text: Rui

text: Yang

text: received

text: the

text: M.S.

text: and

text: Ph.D.

text: de-

text: grees

text: in

text: electrical

text: engineering

text: from

text: the

text: University

text: of

text: Maryland,

text: College

text: Park,

text: in

text: and

text: respec-

text: tively.

text: He

text: has

text: years

text: of

text: experience

text: in

text: the

text: research

text: and

text: development

text: of

text: wireless

text: communication

text: sys-

text: tems.

text: Since

text: he

text: joined

text: InterDigital

text: Communications

text: in

text: he

text: has

text: led

text: several

text: product

text: development

text: and

text: research

text: projects.

text: He

text: is

text: currently

text: a

text: Principle

text: Engineer

text: at

text: InterDigital

text: Labs,

text: leading

text: a

text: project

text: on

text: baseband

text: and

text: RF

text: waveforms

text: for

text: future

text: wireless

text: communication

text: systems.

text: His

text: interests

text: include

text: digital

text: signal

text: processing

text: and

text: air

text: interface

text: design.

text: He

text: has

text: received

text: more

text: than

text: patent

text: awards

text: in

text: those

text: areas.

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##


text: On the stability of some imaging functionals ∗ † ‡ Guillaume Bal Olivier Pinaud Lenya Ryzhik May 27, 2020 Abstract This work is devoted to the stability/resolution analysis of several imaging functionals in complex environments. We consider both linear functionals in the waveﬁeld as well as quadratic functionals based on waveﬁeld correlations. Using simpliﬁed measurement set- tings and reduced functionals that retain the main features of functionals used in practice, we obtain optimal asymptotic estimates of the signal-to-noise ratios depending on the main physical parameters of the problem. We consider random media with possibly long-range dependence and with a correlation length that is less than or equal to the central wave- length of the source we aim to reconstruct. This corresponds to the wave propagation regimes of radiative transfer or homogenization. 1 Introduction Imaging in complex media has a long history with many applications such as non-destructive testing, seismology, or underwater acoustics [16, 28, 3]. Standard methodologies consist in emitting a pulse in the heterogeneous medium and performing measurements of the waveﬁeld or other relevant quantities at an array of detectors. Depending on the experimental setting, this may give access, for instance, to the backscattered waveﬁeld (and its spatio-temporal correlations), or to the wave energy. The imaging procedure then typically amounts to back- propagating the measured data appropriately. When scattering of the wave by the medium is not too strong, measurements are usually migrated in a homogeneous medium neglecting the heterogeneities. This is the principle of the Kirchhoﬀ migration and similar techniques, and is referred to as coherent imaging [11]. When scattering is stronger, the interaction be- tween the wave and the medium cannot be neglected and a diﬀerent model for the inversion is needed. We will only consider weak heterogeneities in this work, so that a homogeneous model is enough to obtain accurate reconstructions. We refer to [10, 8] for a consideration of stronger ﬂuctuations and transport-based imaging. We are interested here in comparing two classes of imaging methods in terms of stability and resolution: one based on the waveﬁeld measurements (and thus linear in the waveﬁelds), such as Kirchhoﬀ migration; and the other one based on correlations of the waveﬁeld (and therefore quadratic in the waveﬁelds), such as coherent interferometry imaging [14]. Here, “stability” refers to the stability of the reconstructions with respect to changes in the medium or to a measurement noise. ∗ Department of Applied Physics and Applied Mathematics, Columbia University, New York NY, 10027 ; gb2030@columbia.edu † Department of Mathematics, Colorado State University, Fort Collins CO, 80523 ; pin- aud@math.colostate.edu ‡ Department of Mathematics, Stanford University, Stanford CA 94305 ; ryzhik@math.stanford.edu 1 ##LTLine##

text: On

text: the

text: stability

text: of

text: some

text: imaging

text: functionals

text: Guillaume

text: Bal

text: Olivier

text: Pinaud

text: Lenya

text: Ryzhik

text: May

text: Abstract

text: This

text: work

text: is

text: devoted

text: to

text: the

text: stability/resolution

text: analysis

text: of

text: several

text: imaging

text: functionals

text: in

text: complex

text: environments.

text: We

text: consider

text: both

text: linear

text: functionals

text: in

text: the

text: waveﬁeld

text: as

text: well

text: as

text: quadratic

text: functionals

text: based

text: on

text: waveﬁeld

text: correlations.

text: Using

text: simpliﬁed

text: measurement

text: set-

text: tings

text: and

text: reduced

text: functionals

text: that

text: retain

text: the

text: main

text: features

text: of

text: functionals

text: used

text: in

text: practice,

text: we

text: obtain

text: optimal

text: asymptotic

text: estimates

text: of

text: the

text: signal-to-noise

text: ratios

text: depending

text: on

text: the

text: main

text: physical

text: parameters

text: of

text: the

text: problem.

text: We

text: consider

text: random

text: media

text: with

text: possibly

text: long-range

text: dependence

text: and

text: with

text: a

text: correlation

text: length

text: that

text: is

text: less

text: than

text: or

text: equal

text: to

text: the

text: central

text: wave-

text: length

text: of

text: the

text: source

text: we

text: aim

text: to

text: reconstruct.

text: This

text: corresponds

text: to

text: the

text: wave

text: propagation

text: regimes

text: of

text: radiative

text: transfer

text: or

text: homogenization.

text: Introduction

text: Imaging

text: in

text: complex

text: media

text: has

text: a

text: long

text: history

text: with

text: many

text: applications

text: such

text: as

text: non-destructive

text: testing,

text: seismology,

text: or

text: underwater

text: acoustics

text: Standard

text: methodologies

text: consist

text: in

text: emitting

text: a

text: pulse

text: in

text: the

text: heterogeneous

text: medium

text: and

text: performing

text: measurements

text: of

text: the

text: waveﬁeld

text: or

text: other

text: relevant

text: quantities

text: at

text: an

text: array

text: of

text: detectors.

text: Depending

text: on

text: the

text: experimental

text: setting,

text: this

text: may

text: give

text: access,

text: for

text: instance,

text: to

text: the

text: backscattered

text: waveﬁeld

text: (and

text: its

text: spatio-temporal

text: correlations),

text: or

text: to

text: the

text: wave

text: energy.

text: The

text: imaging

text: procedure

text: then

text: typically

text: amounts

text: to

text: back-

text: propagating

text: the

text: measured

text: data

text: appropriately.

text: When

text: scattering

text: of

text: the

text: wave

text: by

text: the

text: medium

text: is

text: not

text: too

text: strong,

text: measurements

text: are

text: usually

text: migrated

text: in

text: a

text: homogeneous

text: medium

text: neglecting

text: the

text: heterogeneities.

text: This

text: is

text: the

text: principle

text: of

text: the

text: Kirchhoﬀ

text: migration

text: and

text: similar

text: techniques,

text: and

text: is

text: referred

text: to

text: as

text: coherent

text: imaging

text: When

text: scattering

text: is

text: stronger,

text: the

text: interaction

text: be-

text: tween

text: the

text: wave

text: and

text: the

text: medium

text: cannot

text: be

text: neglected

text: and

text: a

text: diﬀerent

text: model

text: for

text: the

text: inversion

text: is

text: needed.

text: We

text: will

text: only

text: consider

text: weak

text: heterogeneities

text: in

text: this

text: work,

text: so

text: that

text: a

text: homogeneous

text: model

text: is

text: enough

text: to

text: obtain

text: accurate

text: reconstructions.

text: We

text: refer

text: to

text: for

text: a

text: consideration

text: of

text: stronger

text: ﬂuctuations

text: and

text: transport-based

text: imaging.

text: We

text: are

text: interested

text: here

text: in

text: comparing

text: two

text: classes

text: of

text: imaging

text: methods

text: in

text: terms

text: of

text: stability

text: and

text: resolution:

text: one

text: based

text: on

text: the

text: waveﬁeld

text: measurements

text: (and

text: thus

text: linear

text: in

text: the

text: waveﬁelds),

text: such

text: as

text: Kirchhoﬀ

text: migration;

text: and

text: the

text: other

text: one

text: based

text: on

text: correlations

text: of

text: the

text: waveﬁeld

text: (and

text: therefore

text: quadratic

text: in

text: the

text: waveﬁelds),

text: such

text: as

text: coherent

text: interferometry

text: imaging

text: Here,

text: “stability”

text: refers

text: to

text: the

text: stability

text: of

text: the

text: reconstructions

text: with

text: respect

text: to

text: changes

text: in

text: the

text: medium

text: or

text: to

text: a

text: measurement

text: noise.

text: Department

text: of

text: Applied

text: Physics

text: and

text: Applied

text: Mathematics,

text: Columbia

text: University,

text: New

text: York

text: NY,

text: Department

text: of

text: Mathematics,

text: Colorado

text: State

text: University,

text: Fort

text: Collins

text: CO,

text: pin-

text: aud@math.colostate.edu

text: Department

text: of

text: Mathematics,

text: Stanford

text: University,

text: Stanford

text: CA

text: ryzhik@math.stanford.edu

text: ##LTLine##


text: 4 Analysis of the CB functional We compute in this section the mean and the variance of the CB functional. 4.1 Average of the functional Assume for the moment that our measurements have the form, for g a smooth function: ∗ − a = F x g, g(x, k) = g (x c T kˆ, k) := T g (x, k). S ε k 0 0 T 0 Above, F x(k) is the ﬁlter deﬁne(cid:90)d in(cid:90)(3.3) and T is the free transport semigroup introduced ε t in (3.11). Plugging this expression into the CB functional yields: − − IC[g](x) = dkdqF x(k q)g (x + c T (kˆ qˆ)(cid:82), q). R ε 0 0 Dx 3 R Let us verify ﬁrst that when D = 3, we recover that IC[g](x) = (2π)3 R3 dqg|0(x, q|), so that if g is the scalar Wigner transform of a function ψ, we ﬁnd IC[g](x) = (2π)3 ψ(x) 2 and the 0 (cid:82) reconstruction is then perfect. This is immediate since from the deﬁnition of F x(k) given in R ε (3.3) we conclude that F x(k) = (2π)3δ (k) when C = 3. When C is ﬁnite as is the case in ε 0 practical situations, one does not recover R dqg(x, q) but an approximate version of it limited 3 by the resolution of the functional. This point is addressed below. Amplitude and resolution. For simplicity, we suppose that the domain C is chosen such that F x deﬁned in (3.3) is independent of x. We suppose in addition that C is a ball centered ε ∈ ± ∈ at zero of a certain radius. We parametrize C by γ [0, 1] such that if εy C, then we have | | ≤ − 2 εy r ε1 γ for some r > 0. This means that the diameter of the ball is equal to 0 0 − r ε γ := N 0 C where the parameter N was introduced in section . Since the (rescaled) detector has a side C l < 1, we have necessarily by construction that r < l . We could easily accommodate for L 0 L anisotropic domains C with additional technicalities. In order to deal with a regular ﬁlter, we smooth out the characteristic fun(cid:90)ction of the unit disk and rep(cid:18)lace it(cid:19)by some approximate ≡ | | → − function χ(x) χ( x ). Rescaling y as y yr ε γ, it comes for the ﬁlter F : 0 ε | | r3 − · | | r3 r k F (k) = 0 eir0ε γk yχ( y )dy := 0 F 0 . ε ε3γ R ε3γ εγ 3 ∗ Recall that our measurements read a = F x aε, where aε is given by (3.16). The total S ε functional is denoted by IC[aε](x) and its average is given by IC[a¯](x). The mean of the − | | measurements a¯ is the sum of a ballistic term aB(t, x, k) = T aε(x, k)e Σ( k )t and a multiple t 0 scattering term deﬁned in (3.11). Measurements in a homogeneous medium have the form T aε(x, k). The CB functional is tailored to backpropagate the data along the characteristics t 0 of the transport equation, so as to undo the eﬀects of free transport. Since the multiple scattering term is smoother than the ballistic term, one can expect the inversion operation to produce a signal with a lower amplitude for the multiple scattering part than for the ballistic part. We therefore neglect the multiple scattering in the computation of the average functional. Moreover, the resolution of IC is mostly limited by the ﬁlter F and not by the size of the detector since C is included in D. As a consequence, the limitations due to D on the R resolution are negligible and we replace D by 3 in the deﬁnition of IC. We then ﬁnd, x (cid:32) (cid:33) (cid:90) (cid:90) (cid:18) (cid:19) E{ } (cid:39) IC[aε] (x) IC[aB](x) − | − | − (cid:39) µe Σr3 r k q x + kˆ qˆ | | − | | | | 0 F 0 w , µ( q k ) dkd q dqˆ ε3γ R εγ 0 εµ 0 Dx 3 16 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Analysis

text: of

text: the

text: CB

text: functional

text: We

text: compute

text: in

text: this

text: section

text: the

text: mean

text: and

text: the

text: variance

text: of

text: the

text: CB

text: functional.

text: Average

text: of

text: the

text: functional

text: Assume

text: for

text: the

text: moment

text: that

text: our

text: measurements

text: have

text: the

text: form,

text: for

text: g

text: a

text: smooth

text: function:

text: a

text: F

text: x

text: g,

text: g(x,

text: k)

text: g

text: (x

text: c

text: T

text: kˆ,

text: k)

text: T

text: g

text: (x,

text: k).

text: S

text: ε

text: k

text: T

text: Above,

text: F

text: x(k)

text: is

text: the

text: ﬁlter

text: and

text: T

text: is

text: the

text: free

text: transport

text: semigroup

text: introduced

text: ε

text: t

text: in

text: Plugging

text: this

text: expression

text: into

text: the

text: CB

text: functional

text: yields:

text: IC[g](x)

text: dkdqF

text: x(k

text: q)g

text: (x

text: c

text: T

text: (kˆ

text: q).

text: R

text: ε

text: Dx

text: R

text: Let

text: us

text: verify

text: ﬁrst

text: that

text: when

text: D

text: we

text: recover

text: that

text: IC[g](x)

text: q|),

text: so

text: that

text: if

text: g

text: is

text: the

text: scalar

text: Wigner

text: transform

text: of

text: a

text: function

text: ψ,

text: we

text: ﬁnd

text: IC[g](x)

text: ψ(x)

text: and

text: the

text: reconstruction

text: is

text: then

text: perfect.

text: This

text: is

text: immediate

text: since

text: from

text: the

text: deﬁnition

text: of

text: F

text: x(k)

text: given

text: in

text: R

text: ε

text: we

text: conclude

text: that

text: F

text: x(k)

text: (k)

text: when

text: C

text: When

text: C

text: is

text: ﬁnite

text: as

text: is

text: the

text: case

text: in

text: ε

text: practical

text: situations,

text: one

text: does

text: not

text: recover

text: R

text: dqg(x,

text: q)

text: but

text: an

text: approximate

text: version

text: of

text: it

text: limited

text: by

text: the

text: resolution

text: of

text: the

text: functional.

text: This

text: point

text: is

text: addressed

text: below.

text: Amplitude

text: and

text: resolution.

text: For

text: simplicity,

text: we

text: suppose

text: that

text: the

text: domain

text: C

text: is

text: chosen

text: such

text: that

text: F

text: x

text: deﬁned

text: in

text: is

text: independent

text: of

text: x.

text: We

text: suppose

text: in

text: addition

text: that

text: C

text: is

text: a

text: ball

text: centered

text: ε

text: at

text: zero

text: of

text: a

text: certain

text: radius.

text: We

text: parametrize

text: C

text: by

text: γ

text: such

text: that

text: if

text: εy

text: C,

text: then

text: we

text: have

text: εy

text: r

text: ε1

text: γ

text: for

text: some

text: r

text: This

text: means

text: that

text: the

text: diameter

text: of

text: the

text: ball

text: is

text: equal

text: to

text: r

text: ε

text: γ

text: N

text: C

text: where

text: the

text: parameter

text: N

text: was

text: introduced

text: in

text: section

text: Since

text: the

text: (rescaled)

text: detector

text: has

text: a

text: side

text: C

text: l

text: we

text: have

text: necessarily

text: by

text: construction

text: that

text: r

text: l

text: We

text: could

text: easily

text: accommodate

text: for

text: L

text: L

text: anisotropic

text: domains

text: C

text: with

text: additional

text: technicalities.

text: In

text: order

text: to

text: deal

text: with

text: a

text: regular

text: ﬁlter,

text: we

text: smooth

text: out

text: the

text: characteristic

text: of

text: the

text: unit

text: disk

text: and

text: some

text: approximate

text: function

text: χ(x)

text: χ(

text: x

text: Rescaling

text: y

text: as

text: y

text: yr

text: ε

text: γ,

text: it

text: comes

text: for

text: the

text: ﬁlter

text: F

text: ε

text: r

text: k

text: F

text: (k)

text: γk

text: yχ(

text: y

text: )dy

text: F

text: ε

text: ε3γ

text: R

text: ε3γ

text: εγ

text: Recall

text: that

text: our

text: measurements

text: read

text: a

text: F

text: x

text: aε,

text: where

text: aε

text: is

text: given

text: by

text: The

text: total

text: S

text: ε

text: functional

text: is

text: denoted

text: by

text: IC[aε](x)

text: and

text: its

text: average

text: is

text: given

text: by

text: IC[a¯](x).

text: The

text: mean

text: of

text: the

text: measurements

text: a¯

text: is

text: the

text: sum

text: of

text: a

text: ballistic

text: term

text: aB(t,

text: x,

text: k)

text: T

text: aε(x,

text: k)e

text: Σ(

text: k

text: )t

text: and

text: a

text: multiple

text: t

text: scattering

text: term

text: deﬁned

text: in

text: Measurements

text: in

text: a

text: homogeneous

text: medium

text: have

text: the

text: form

text: T

text: aε(x,

text: k).

text: The

text: CB

text: functional

text: is

text: tailored

text: to

text: backpropagate

text: the

text: data

text: along

text: the

text: characteristics

text: t

text: of

text: the

text: transport

text: equation,

text: so

text: as

text: to

text: undo

text: the

text: eﬀects

text: of

text: free

text: transport.

text: Since

text: the

text: multiple

text: scattering

text: term

text: is

text: smoother

text: than

text: the

text: ballistic

text: term,

text: one

text: can

text: expect

text: the

text: inversion

text: operation

text: to

text: produce

text: a

text: signal

text: with

text: a

text: lower

text: amplitude

text: for

text: the

text: multiple

text: scattering

text: part

text: than

text: for

text: the

text: ballistic

text: part.

text: We

text: therefore

text: neglect

text: the

text: multiple

text: scattering

text: in

text: the

text: computation

text: of

text: the

text: average

text: functional.

text: Moreover,

text: the

text: resolution

text: of

text: IC

text: is

text: mostly

text: limited

text: by

text: the

text: ﬁlter

text: F

text: and

text: not

text: by

text: the

text: size

text: of

text: the

text: detector

text: since

text: C

text: is

text: included

text: in

text: D.

text: As

text: a

text: consequence,

text: the

text: limitations

text: due

text: to

text: D

text: on

text: the

text: R

text: resolution

text: are

text: negligible

text: and

text: we

text: replace

text: D

text: by

text: in

text: the

text: deﬁnition

text: of

text: IC.

text: We

text: then

text: ﬁnd,

text: x

text: E{

text: IC[aε]

text: (x)

text: IC[aB](x)

text: µe

text: r

text: k

text: q

text: x

text: kˆ

text: qˆ

text: F

text: w

text: µ(

text: q

text: k

text: dkd

text: q

text: dqˆ

text: ε3γ

text: R

text: εγ

text: εµ

text: Dx

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##