text: A revised version of this manuscript was published in CMIG (PMID: 18982583). Please cite the ﬁnal version: “Computational Pathology: Challenges and Promises for Tissue Analysis”, Thomas J. Fuchs and Joachim M. Buhmann, Computerized Medical Imaging and Graphics, Volume 35, Issue 7, 515–530, 2011. (a) (b) (c) (d) Figure 4: (a) A quarter of an RCC TMA spot used for the nuclei detec- tion experiment. (b) Annotations of one expert, indicating abnormal nuclei in black and normal ones in red. (c) Overlay of detected nuclei from expert one (blue circles) and expert two (red crosses). (d) Dis- agreement between the two domain experts regarding the detection task. Nuclei which were labeled only by pathologist one are shown in blue and the nuclei found only by expert two are depicted in red. Complementary to immunohistochemical TMA anal- ysis, ﬂuorescence microscopy is applied often for high- throughput screening of molecular phenotypes. A com- Figure 3: Tablet PC labeling applications for (i) global staining esti- prehensive study evaluating the performance of domain mation (ii) nuclei detection and (iii) nuclei classiﬁcation (from top to bottom). experts regarding the detection of lymphocytes is pre- sented by [12]. In a best case, a medium-skilled ex- pert needs on average one hour for analyzing a ﬂuores- cence micrograph. Each micrograph contains between The estimations of the experts varied by up to 20% as × 100 and 400 cells and is of size 658 517 pixel. Four shown in Figure 6b. As depicted in Figure 6b the stan- exemplary micrographs were blindly evaluated by ﬁve dard deviation between the experts grows linearly with experts. To evaluate the inter-observer variability nat- the average estimated amount of staining. The high vari- tkemper et al. [12] deﬁne a gold standard comprising ability demonstrates the subjectivity of the estimation all cell positions in a micrograph that were detected by process. This uncertainty is especially critical for types at least two experts. of cancer for which the clinician chooses the therapy Averaged over of CD3, CD4, CD7 and CD8 the sen- based on the estimated staining percentage. This result sitivity of the four biomedical experts is varying be- not only motivates but emphasizes the need for more ob- jective estimation procedures than current practice. Our tween 67.5% and 91.2% and the positive predictive value (PPV) between 75% and 100%. Thus the average research is stimulated by the hope, that computational detection error over all biomedical experts and micro- pathology approaches do not only automated such esti- graphs is approximately 17%. Although ﬂuorescence mation processes but also produce better reproduceable images appear to be easier to analyze due to their homo- and more objective results than human judgment. geneous background, this high detection error indicates 2.4. Expert Variability in Fluorescence Microscopy the difﬁculty of this analysis task. These results corrob- 5 Preprint, June 29, 2010 ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTLine##

text: A

text: revised

text: version

text: of

text: this

text: manuscript

text: was

text: published

text: in

text: CMIG

text: (PMID:

text: Please

text: cite

text: the

text: ﬁnal

text: version:

text: “Computational

text: Pathology:

text: Challenges

text: and

text: Promises

text: for

text: Tissue

text: Analysis”,

text: Thomas

text: J.

text: Fuchs

text: and

text: Joachim

text: M.

text: Buhmann,

text: Computerized

text: Medical

text: Imaging

text: and

text: Graphics,

text: Volume

text: Issue

text: (a)

text: (b)

text: (c)

text: (d)

text: Figure

text: (a)

text: A

text: quarter

text: of

text: an

text: RCC

text: TMA

text: spot

text: used

text: for

text: the

text: nuclei

text: detec-

text: tion

text: experiment.

text: (b)

text: Annotations

text: of

text: one

text: expert,

text: indicating

text: abnormal

text: nuclei

text: in

text: black

text: and

text: normal

text: ones

text: in

text: red.

text: (c)

text: Overlay

text: of

text: detected

text: nuclei

text: from

text: expert

text: one

text: (blue

text: circles)

text: and

text: expert

text: two

text: (red

text: crosses).

text: (d)

text: Dis-

text: agreement

text: between

text: the

text: two

text: domain

text: experts

text: regarding

text: the

text: detection

text: task.

text: Nuclei

text: which

text: were

text: labeled

text: only

text: by

text: pathologist

text: one

text: are

text: shown

text: in

text: blue

text: and

text: the

text: nuclei

text: found

text: only

text: by

text: expert

text: two

text: are

text: depicted

text: in

text: red.

text: Complementary

text: to

text: immunohistochemical

text: TMA

text: anal-

text: ysis,

text: ﬂuorescence

text: microscopy

text: is

text: applied

text: often

text: for

text: high-

text: throughput

text: screening

text: of

text: molecular

text: phenotypes.

text: A

text: com-

text: Figure

text: Tablet

text: PC

text: labeling

text: applications

text: for

text: (i)

text: global

text: staining

text: esti-

text: prehensive

text: study

text: evaluating

text: the

text: performance

text: of

text: domain

text: mation

text: (ii)

text: nuclei

text: detection

text: and

text: (iii)

text: nuclei

text: classiﬁcation

text: (from

text: top

text: to

text: bottom).

text: experts

text: regarding

text: the

text: detection

text: of

text: lymphocytes

text: is

text: pre-

text: sented

text: by

text: In

text: a

text: best

text: case,

text: a

text: medium-skilled

text: ex-

text: pert

text: needs

text: on

text: average

text: one

text: hour

text: for

text: analyzing

text: a

text: ﬂuores-

text: cence

text: micrograph.

text: Each

text: micrograph

text: contains

text: between

text: The

text: estimations

text: of

text: the

text: experts

text: varied

text: by

text: up

text: to

text: as

text: and

text: cells

text: and

text: is

text: of

text: size

text: pixel.

text: Four

text: shown

text: in

text: Figure

text: As

text: depicted

text: in

text: Figure

text: the

text: stan-

text: exemplary

text: micrographs

text: were

text: blindly

text: evaluated

text: by

text: ﬁve

text: dard

text: deviation

text: between

text: the

text: experts

text: grows

text: linearly

text: with

text: experts.

text: To

text: evaluate

text: the

text: inter-observer

text: variability

text: nat-

text: the

text: average

text: estimated

text: amount

text: of

text: staining.

text: The

text: high

text: vari-

text: tkemper

text: et

text: al.

text: deﬁne

text: a

text: gold

text: standard

text: comprising

text: ability

text: demonstrates

text: the

text: subjectivity

text: of

text: the

text: estimation

text: all

text: cell

text: positions

text: in

text: a

text: micrograph

text: that

text: were

text: detected

text: by

text: process.

text: This

text: uncertainty

text: is

text: especially

text: critical

text: for

text: types

text: at

text: least

text: two

text: experts.

text: of

text: cancer

text: for

text: which

text: the

text: clinician

text: chooses

text: the

text: therapy

text: Averaged

text: over

text: of

text: and

text: the

text: sen-

text: based

text: on

text: the

text: estimated

text: staining

text: percentage.

text: This

text: result

text: sitivity

text: of

text: the

text: four

text: biomedical

text: experts

text: is

text: varying

text: be-

text: not

text: only

text: motivates

text: but

text: emphasizes

text: the

text: need

text: for

text: more

text: ob-

text: jective

text: estimation

text: procedures

text: than

text: current

text: practice.

text: Our

text: tween

text: and

text: and

text: the

text: positive

text: predictive

text: value

text: (PPV)

text: between

text: and

text: Thus

text: the

text: average

text: research

text: is

text: stimulated

text: by

text: the

text: hope,

text: that

text: computational

text: detection

text: error

text: over

text: all

text: biomedical

text: experts

text: and

text: micro-

text: pathology

text: approaches

text: do

text: not

text: only

text: automated

text: such

text: esti-

text: graphs

text: is

text: approximately

text: Although

text: ﬂuorescence

text: mation

text: processes

text: but

text: also

text: produce

text: better

text: reproduceable

text: images

text: appear

text: to

text: be

text: easier

text: to

text: analyze

text: due

text: to

text: their

text: homo-

text: and

text: more

text: objective

text: results

text: than

text: human

text: judgment.

text: geneous

text: background,

text: this

text: high

text: detection

text: error

text: indicates

text: Expert

text: Variability

text: in

text: Fluorescence

text: Microscopy

text: the

text: difﬁculty

text: of

text: this

text: analysis

text: task.

text: These

text: results

text: corrob-

text: Preprint,

text: June

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTLine##


text: the Bhattacharya-Mesner (BM) algebra ﬁrst developed in [MB90, MB94] and the general BM al- gebra ﬁrst proposed in [GER11]. The general BM product is of interest because it encompasses as special cases many other hypermatrix products discussed in the literature including the usual matrix product, the Segre outer product, the contraction product, the higher order singular value decomposition, and the multilinear matrix multiplication. The study of structured dense matrices such as discrete Fourier matrices, Hadamard matrices, Hankel matrices, Hessian matrices, Vandermonde matrices, Wronksian matrices, as well as matrix direct sum and Kronecker product constructions play important roles in the applications of lin- ear algebra methods to other disciplines. Many established results concerning such matrices draw heavily on matrix spectral analysis toolkits which include techniques derived from matrix spec- tral decompositions, Fourier-Hadamard–Rademacher–Walsh transforms, the Parseval’s identity, the Gram–Schmidt orthogonalization process and the Rayleigh quotient inequality. The development of hypermatrix spectral analysis toolkits constitutes the main obstacle to extending these results to hypermatrices. The present work aims to add to hypermatrix spectral analysis toolkits. Our main result is a constructive method for obtaining spectral decomposition of hypermatrix direct sum and Kronecker product constructions. The method is based in part on a generalization of Parseval’s identity. We use this general formulation of Parseval’s identity to introduce hyperma- trix Fourier transforms and discrete Fourier hypermatrices. We extend to hypermatrices a variant of the Gram–Schmidt orthogonalization process as well as Sylvester’s classical Hadamard matrix construction. We conclude the paper with illustrations of spectral decompositions of adjacency hypermatrices of ﬁnite groups and a short proof of the hypermatrix Rayleigh quotient inequality. This article is accompanied by an extensive and actively maintained Sage [S+15] symbolic hyperma- trix algebra package which implements the various features of the general BM algebra. The package is made available at the link https://github.com/gnang/HypermatrixAlgebraPackage Acknowledgement: We would like to thank Andrei Gabrielov for providing guidance while preparing this manuscript. We would like to thank Vladimir Retakh and Ahmed Elgammal for patiently in- troducing us to the theory of hypermatrices. We are grateful to Doron Zeilberger and Saugata Basu for helpful suggestions. We would like to thank Ori Parzanchevski for helping get the hypermatrix package started. The second author was supported by the National Science Foundation, and is grateful for the hospitality of the Institute for Advanced Study and the Department of Mathematics at Purdue University. 2 Overview of the BM algebra The Bhattacharya-Mesner product, or BM product for short, was ﬁrst developed in [MB90, MB94]. (cid:0) (cid:1) The BM product provides a natural generalization to the matrix product. The BM product of second order hypermatrices corresponds to the usual matrix product. For notational consistency, · we will on occasion use the notation Prod A(1), A(2) to refer to the matrix product A(1) A(2). The BM product is best introduced to the unfamiliar reader by ﬁrst describing the BM product of third and fourth order hypermatrices. Note that the BM product of second order hypermatrices is a binary operation, the BM product of third order hypermatrices is a ternary operation, the BM 2

text: the

label: paragraph

text: Bhattacharya-Mesner

text: (BM)

text: algebra

text: ﬁrst

text: developed

text: in

text: and

text: the

text: general

text: BM

text: al-

text: gebra

text: ﬁrst

text: proposed

text: in

text: The

text: general

text: BM

text: product

text: is

text: of

text: interest

text: because

text: it

text: encompasses

text: as

text: special

text: cases

text: many

text: other

text: hypermatrix

text: products

text: discussed

text: in

text: the

text: literature

text: including

text: the

text: usual

text: matrix

text: product,

text: the

text: Segre

text: outer

text: product,

text: the

text: contraction

text: product,

text: the

text: higher

text: order

text: singular

text: value

text: decomposition,

text: and

text: the

text: multilinear

text: matrix

text: multiplication.

text: The

text: study

text: of

text: structured

text: dense

text: matrices

text: such

text: as

text: discrete

text: Fourier

text: matrices,

text: Hadamard

text: matrices,

text: Hankel

text: matrices,

text: Hessian

text: matrices,

text: Vandermonde

text: matrices,

text: Wronksian

text: matrices,

text: as

text: well

text: as

text: matrix

text: direct

text: sum

text: and

text: Kronecker

text: product

text: constructions

text: play

text: important

text: roles

text: in

text: the

text: applications

text: of

text: lin-

text: ear

text: algebra

text: methods

text: to

text: other

text: disciplines.

text: Many

text: established

text: results

text: concerning

text: such

text: matrices

text: draw

text: heavily

text: on

text: matrix

text: spectral

text: analysis

text: toolkits

text: which

text: include

text: techniques

text: derived

text: from

text: matrix

text: spec-

text: tral

text: decompositions,

text: Fourier-Hadamard–Rademacher–Walsh

text: transforms,

text: the

text: Parseval’s

text: identity,

text: the

text: Gram–Schmidt

text: orthogonalization

text: process

text: and

text: the

text: Rayleigh

text: quotient

text: inequality.

text: The

text: development

text: of

text: hypermatrix

text: spectral

text: analysis

text: toolkits

text: constitutes

text: the

text: main

text: obstacle

text: to

text: extending

text: these

text: results

text: to

text: hypermatrices.

text: The

text: present

text: work

text: aims

text: to

text: add

text: to

text: hypermatrix

text: spectral

text: analysis

text: toolkits.

text: Our

text: main

text: result

text: is

text: a

text: constructive

text: method

text: for

text: obtaining

text: spectral

text: decomposition

text: of

text: hypermatrix

text: direct

text: sum

text: and

text: Kronecker

text: product

text: constructions.

text: The

text: method

text: is

text: based

text: in

text: part

text: on

text: a

text: generalization

text: of

text: Parseval’s

text: identity.

text: We

text: use

text: this

text: general

text: formulation

text: of

text: Parseval’s

text: identity

text: to

text: introduce

text: hyperma-

text: trix

text: Fourier

text: transforms

text: and

text: discrete

text: Fourier

text: hypermatrices.

text: We

text: extend

text: to

text: hypermatrices

text: a

text: variant

text: of

text: the

text: Gram–Schmidt

text: orthogonalization

text: process

text: as

text: well

text: as

text: Sylvester’s

text: classical

text: Hadamard

text: matrix

text: construction.

text: We

text: conclude

text: the

text: paper

text: with

text: illustrations

text: of

text: spectral

text: decompositions

text: of

text: adjacency

text: hypermatrices

text: of

text: ﬁnite

text: groups

text: and

text: a

text: short

text: proof

text: of

text: the

text: hypermatrix

text: Rayleigh

text: quotient

text: inequality.

text: This

text: article

text: is

text: accompanied

text: by

text: an

text: extensive

text: and

text: actively

text: maintained

text: Sage

text: symbolic

text: hyperma-

text: trix

text: algebra

text: package

text: which

text: implements

text: the

text: various

text: features

text: of

text: the

text: general

text: BM

text: algebra.

text: The

text: package

text: is

text: made

text: available

text: at

text: the

text: link

text: Acknowledgement:

text: We

text: would

text: like

text: to

text: thank

text: Andrei

text: Gabrielov

text: for

text: providing

text: guidance

text: while

text: preparing

text: this

text: manuscript.

text: We

text: would

text: like

text: to

text: thank

text: Vladimir

text: Retakh

text: and

text: Ahmed

text: Elgammal

text: for

text: patiently

text: in-

text: troducing

text: us

text: to

text: the

text: theory

text: of

text: hypermatrices.

text: We

text: are

text: grateful

text: to

text: Doron

text: Zeilberger

text: and

text: Saugata

text: Basu

text: for

text: helpful

text: suggestions.

text: We

text: would

text: like

text: to

text: thank

text: Ori

text: Parzanchevski

text: for

text: helping

text: get

text: the

text: hypermatrix

text: package

text: started.

text: The

text: second

text: author

text: was

text: supported

text: by

text: the

text: National

text: Science

text: Foundation,

text: and

text: is

text: grateful

text: for

text: the

text: hospitality

text: of

text: the

text: Institute

text: for

text: Advanced

text: Study

text: and

text: the

text: Department

text: of

text: Mathematics

text: at

text: Purdue

text: University.

text: Overview

text: of

text: the

text: BM

text: algebra

text: The

text: Bhattacharya-Mesner

text: product,

text: or

text: BM

text: product

text: for

text: short,

text: was

text: ﬁrst

text: developed

text: in

text: The

text: BM

text: product

text: provides

text: a

text: natural

text: generalization

text: to

text: the

text: matrix

text: product.

text: The

text: BM

text: product

text: of

text: second

text: order

text: hypermatrices

text: corresponds

text: to

text: the

text: usual

text: matrix

text: product.

text: For

text: notational

text: consistency,

text: we

text: will

text: on

text: occasion

text: use

text: the

text: notation

text: Prod

text: to

text: refer

text: to

text: the

text: matrix

text: product

text: The

text: BM

text: product

text: is

text: best

text: introduced

text: to

text: the

text: unfamiliar

text: reader

text: by

text: ﬁrst

text: describing

text: the

text: BM

text: product

text: of

text: third

text: and

text: fourth

text: order

text: hypermatrices.

text: Note

text: that

text: the

text: BM

text: product

text: of

text: second

text: order

text: hypermatrices

text: is

text: a

text: binary

text: operation,

text: the

text: BM

text: product

text: of

text: third

text: order

text: hypermatrices

text: is

text: a

text: ternary

text: operation,

text: the

text: BM


text: (cid:0) (cid:1) and the sought after result follows (cid:62) ≤ Prod x , y ≤ (cid:3) A 0m≤ti<nn λt Prod (x(cid:62), y) 0m≤ta<xn λt . ≤ ≤ · · · ≤ ≤ By sorting the eigenvalues such that λ λ λ − λ − It is then easily veriﬁed that the 0 1 n 2 n 1 bounds are attained for the choices x = V [:, 0] , y = U [:, 0] and − − x = V [:, n 1] , y = U [:, n 1] . (cid:92) It is useful to provide some explicit description for vectors in the set ⊂ C × × C × S n 1 n 1. k ≤ 0 k<n (cid:92) (cid:88) (cid:88) The explicit description is given by (x, y) ∈ S ⇔ x = α V [:, i] , y = β U [:, j] s.t. {α β } ≤ ⊂ R≥ . k i j k k 0 k<n 0 ≤ ≤ ≤ 0 k<n 0 i<n 0 j<n Having discussed the matrix formulation of the general Rayleigh quotient, we now discuss the hyper- matrix formulation of the Rayleigh quotient. For notational convenience we restrict the discussion to third order hypermatrices, but the formulation extends to hypermatrices of all orders. (cid:18) (cid:19) Theorem 9 : Let A ∈ Cn×n(cid:16)×n, whose s(cid:17)pectral (cid:16)decompositi(cid:17)on is given(cid:16)by (cid:17) (cid:62) (cid:62) (cid:62) (cid:62) 2 (cid:62) A = Prod Prod U, D , D , Prod V, D , D , Prod W, D , D 0 0 1 1 2 2 (cid:40) (cid:104) (cid:16) (cid:17)(cid:105) subject to ≤ U, V, W ∈ Cn×n×n and Prod U, V(cid:62)2, W(cid:62) = 1 if 0 i = j = k < n , (cid:40) i,j,k 0 otherwise where ≥ ≤ µ = µ 0 if 0 i = k < n (cid:40) jk kj [D ] = , 0 ijk 0 otherwise ≥ ≤ ν = ν 0 if 0 i = k < n (cid:40) jk kj [D ] = , 1 ijk 0 otherwise ≥ ≤ ω = ω 0 if 0 i = k < n jk kj [D ] = . 2 ijk 0 otherwise 32 ##LTLine##

text: and

text: the

text: sought

text: after

text: result

text: follows

text: Prod

text: x

text: y

text: A

text: λt

text: Prod

text: y)

text: λt

text: By

text: sorting

text: the

text: eigenvalues

text: such

text: that

text: λ

text: λ

text: λ

text: λ

text: It

text: is

text: then

text: easily

text: veriﬁed

text: that

text: the

text: n

text: n

text: bounds

text: are

text: attained

text: for

text: the

text: choices

text: x

text: V

text: y

text: U

text: and

text: x

text: V

text: n

text: y

text: U

text: n

text: It

text: is

text: useful

text: to

text: provide

text: some

text: explicit

text: description

text: for

text: vectors

text: in

text: the

text: set

text: C

text: C

text: S

text: n

text: n

text: k

text: k<n

text: The

text: explicit

text: description

text: is

text: given

text: by

text: (x,

text: y)

text: S

text: x

text: α

text: V

text: i]

text: y

text: β

text: U

text: j]

text: s.t.

text: {α

text: β

text: R≥

text: k

text: i

text: j

text: k

text: k

text: k<n

text: k<n

text: i<n

text: j<n

text: Having

text: discussed

text: the

text: matrix

text: formulation

text: of

text: the

text: general

text: Rayleigh

text: quotient,

text: we

text: now

text: discuss

text: the

text: hyper-

text: matrix

text: formulation

text: of

text: the

text: Rayleigh

text: quotient.

text: For

text: notational

text: convenience

text: we

text: restrict

text: the

text: discussion

text: to

text: third

text: order

text: hypermatrices,

text: but

text: the

text: formulation

text: extends

text: to

text: hypermatrices

text: of

text: all

text: orders.

text: Theorem

text: Let

text: A

text: whose

text: is

text: A

text: Prod

text: Prod

text: U,

text: D

text: D

text: Prod

text: V,

text: D

text: D

text: Prod

text: W,

text: D

text: D

text: subject

text: to

text: U,

text: V,

text: W

text: Cn×n×n

text: and

text: Prod

text: U,

text: if

text: i

text: j

text: k

text: n

text: i,j,k

text: otherwise

text: where

text: µ

text: µ

text: if

text: i

text: k

text: n

text: jk

text: kj

text: [D

text: ijk

text: otherwise

text: ν

text: ν

text: if

text: i

text: k

text: n

text: jk

text: kj

text: [D

text: ijk

text: otherwise

text: ω

text: ω

text: if

text: i

text: k

text: n

text: jk

text: kj

text: [D

text: ijk

text: otherwise

text: ##LTLine##


text: (cid:16) (cid:17) (cid:16) (cid:17) (cid:16) (cid:17) The identity (3) generalizes the matrix transpose identity (cid:62) (cid:62) (cid:62) · · A(1) A(2) = A(2) A(1) . (cid:0) (cid:1) Finally, for notational convenience, we brieﬂy discuss the use of the general BM product to ex- press multilinear forms and outer products. Let A ∈ Cn0×···×nm−1 denote an arbitrary order m hypermatrix and consider an(cid:16) arbitrary m-tuple xj ∈ Cnj×1×···×1 0≤j<m. T(cid:17)he general BM product (cid:62) − (cid:62) − · · · (cid:62) · · · (cid:62) (cid:62) Prod x (m 1), x (m 2), , x j− − , , x 1− , x 0− , A 0 1 m j 1 m 2 m 1 expresses the multilinear form associated with A. As illustration, consider an arbitrary third order hypermatrix A ∈ Cm×n×p a(cid:16)nd three vect(cid:17)ors x(cid:88)∈ Cm(cid:88)×1×1, (cid:88)y ∈ Cn×1×1 and z ∈ Cp×1×1 . The corresponding multilinear form is expressed as (cid:62) (cid:62) (cid:62) Prod x 2, y 1, z 0 = a x y z . A ijk i j k ≤ ≤ ≤ 0 i<m 0 j<n 0 k<p Similarly, for an arbitrary m(cid:16)atrix A (cid:17)∈ Cm(cid:88)×n an(cid:88)d pair of vectors x ∈ Cm×1, y ∈ Cn×1, the corresponding bilinear form is expressed by (cid:62) (cid:62) (cid:62) · · Prod x 1, y 0 = a x y = x A y. A ij i j ≤ ≤ (cid:0) (cid:1)0 i<m 0 j<n The general BM product also provides a convenient way to express outer products. For an arbitrary · · · BM conformable m-tuple A(1), , A(m) , a BM outer product corresponds to a product of the (cid:16) (cid:17) form · · · · · · · · · − · · · · · · Prod A(1) [:, t, :, , :] , A(2) [:, :, t, , :] , , A(m 1) [:, :, , t] , A(m) [t, :, , :] . (4) · · · In (4) we used the colon notation. Recall that in the colon notation, A(1) [:, t, :, , :] refers to × × × · · · × a hypermatrix slice of size n 1 n n where the second index is ﬁxed to t while all 1 3 m other indices are allowed to vary within their prescribed ranges. Hypermatrix outer products are a (cid:110) (cid:111) common occurrence throughout our discussion. Fortunately, hypermatrix outer products are conve- niently expressed in terms of general BM products. The corresponding background hypermatrices are noted ∆(t) ≤ (cid:104) and(cid:105)speciﬁed e(cid:40)ntry-wise by 0 t<n ≤ · · · 1 if 0 t = i = = i < k ∆(t) i1,···,im = 0 oth1erwise m(cid:0) . (cid:1) · · · The outer product in (4) is more conveniently expressed as Prod A(1), , A(m) . This expres- ∆(t) sion of outer products induces a natural notion of hypermatrix BM rank. Using this notation, recall 5

text: The

text: identity

text: generalizes

text: the

text: matrix

text: transpose

text: identity

text: Finally,

text: for

text: notational

text: convenience,

text: we

text: brieﬂy

text: discuss

text: the

text: use

text: of

text: the

text: general

text: BM

text: product

text: to

text: ex-

text: press

text: multilinear

text: forms

text: and

text: outer

text: products.

text: Let

text: A

text: Cn0×···×nm−1

text: denote

text: an

text: arbitrary

text: order

text: m

text: hypermatrix

text: and

text: consider

text: arbitrary

text: m-tuple

text: xj

text: Cnj×1×···×1

text: general

text: BM

text: product

text: Prod

text: x

text: (m

text: x

text: (m

text: x

text: j−

text: x

text: 1−

text: x

text: 0−

text: A

text: m

text: j

text: m

text: m

text: expresses

text: the

text: multilinear

text: form

text: associated

text: with

text: A.

text: As

text: illustration,

text: consider

text: an

text: arbitrary

text: third

text: order

text: hypermatrix

text: A

text: Cm×n×p

text: three

text: and

text: z

text: The

text: corresponding

text: multilinear

text: form

text: is

text: expressed

text: as

text: Prod

text: x

text: y

text: z

text: a

text: x

text: y

text: z

text: A

text: ijk

text: i

text: j

text: k

text: i<m

text: j<n

text: k<p

text: Similarly,

text: for

text: an

text: arbitrary

text: A

text: pair

text: of

text: vectors

text: x

text: y

text: the

text: corresponding

text: bilinear

text: form

text: is

text: expressed

text: by

text: Prod

text: x

text: y

text: a

text: x

text: y

text: x

text: A

text: y.

text: A

text: ij

text: i

text: j

text: i<m

text: j<n

text: The

text: general

text: BM

text: product

text: also

text: provides

text: a

text: convenient

text: way

text: to

text: express

text: outer

text: products.

text: For

text: an

text: arbitrary

text: BM

text: conformable

text: m-tuple

text: A(m)

text: a

text: BM

text: outer

text: product

text: corresponds

text: to

text: a

text: product

text: of

text: the

text: form

text: Prod

text: t,

text: t,

text: A(m

text: t]

text: A(m)

text: [t,

text: In

text: we

text: used

text: the

text: colon

text: notation.

text: Recall

text: that

text: in

text: the

text: colon

text: notation,

text: t,

text: refers

text: to

text: a

text: hypermatrix

text: slice

text: of

text: size

text: n

text: n

text: n

text: where

text: the

text: second

text: index

text: is

text: ﬁxed

text: to

text: t

text: while

text: all

text: m

text: other

text: indices

text: are

text: allowed

text: to

text: vary

text: within

text: their

text: prescribed

text: ranges.

text: Hypermatrix

text: outer

text: products

text: are

text: a

text: common

text: occurrence

text: throughout

text: our

text: discussion.

text: Fortunately,

text: hypermatrix

text: outer

text: products

text: are

text: conve-

text: niently

text: expressed

text: in

text: terms

text: of

text: general

text: BM

text: products.

text: The

text: corresponding

text: background

text: hypermatrices

text: are

text: noted

text: ∆(t)

text: by

text: t<n

text: if

text: t

text: i

text: i

text: k

text: ∆(t)

text: The

text: outer

text: product

text: in

text: is

text: more

text: conveniently

text: expressed

text: as

text: Prod

text: A(m)

text: This

text: expres-

text: ∆(t)

text: sion

text: of

text: outer

text: products

text: induces

text: a

text: natural

text: notion

text: of

text: hypermatrix

text: BM

text: rank.

text: Using

text: this

text: notation,

text: recall


text: (Again, it is not hard to check that any solution to this system satisﬁes (6).) Both matrix and hypermatrix orthogonalization constraints in (7) and (8) turn out to be monomial constraints. General monomial constraints correspond to a system of equations which can be expressed in terms of a coeﬃcient matrix A ∈ Cm×n, a right-hand side vector b ∈ Cm×1, and an unknown vector x of ×    size n 1. These constraints are ofthe f(cid:89)orm      xait = b . (9) t i ≤ 0 t<n ≤ ≤ 1 i m Such constraints are in fact linear constraints as seen by taking the logarithm on both sides of the equal sign of each constraint. We refer to the equivalent system obtained by taking the logarithm as the logarithmic version of the constraints. We solve such systems without using logarithms to avoid any diﬃculty related to branching of the logarithm. Instead, we solve such systems using a slight variation of the Gauss–Jordan elimination algorithm, prescribed by the following elementary row operations: • ↔ Row exchange : R R i j • → Row scaling : (R )k R i i • Row linear combination : (R )k · (R ) → R (cid:16)(cid:81) (cid:17) i j j where k ∈ C and R denotes the particular constraint ≤ xait = b . i 0 t<n t i The proposed modiﬁed row operations perform the usual row operations prescribed by the Gauss–Jordan elimination algorithm on the logarithmic version of the constraints. Proposition 2a: The solution X to the orthogonalization constraints for a generic2 input hyper- matrix A yields a non-trivial orthogonal hypermatrix after normalizing of the rows of the solution matrix X. Proof : The proof follows directly from the Gaussian elimination procedure. The row echelon form of the constraints are obtained by performing the modiﬁed row linear combination operations described earlier in order to put the logarithmic version of the constraints in row echelon form. We deduce from the expression in row echelon form of the orthogonalization constraints (7),(8) a criterion for establishing the existence of solutions in terms of a single polynomial in the entries of A which should be diﬀerent from zero for some input. This condition will be generically satisﬁed, thereby establishing the desired result. 2A generic hypermatrix is one whose entries do not satisfy any particular algebraic relation. 10 ##LTLine##

text: (Again,

text: it

text: is

text: not

text: hard

text: to

text: check

text: that

text: any

text: solution

text: to

text: this

text: system

text: satisﬁes

text: Both

text: matrix

text: and

text: hypermatrix

text: orthogonalization

text: constraints

text: in

text: and

text: turn

text: out

text: to

text: be

text: monomial

text: constraints.

text: General

text: monomial

text: constraints

text: correspond

text: to

text: a

text: system

text: of

text: equations

text: which

text: can

text: be

text: expressed

text: in

text: terms

text: of

text: a

text: coeﬃcient

text: matrix

text: A

text: Cm×n,

text: a

text: right-hand

text: side

text: vector

text: b

text: and

text: an

text: unknown

text: vector

text: x

text: of

label: equation

text: size

text: n

text: These

text: constraints

text: are

text: ofthe

text: xait

text: b

text: t

text: i

text: t<n

text: i

text: m

text: Such

text: constraints

text: are

text: in

text: fact

text: linear

text: constraints

text: as

text: seen

text: by

text: taking

text: the

text: logarithm

text: on

text: both

text: sides

text: of

text: the

text: equal

text: sign

text: of

text: each

text: constraint.

text: We

text: refer

text: to

text: the

text: equivalent

text: system

text: obtained

text: by

text: taking

text: the

text: logarithm

text: as

text: the

text: logarithmic

text: version

text: of

text: the

text: constraints.

text: We

text: solve

text: such

text: systems

text: without

text: using

text: logarithms

text: to

text: avoid

text: any

text: diﬃculty

text: related

text: to

text: branching

text: of

text: the

text: logarithm.

text: Instead,

text: we

text: solve

text: such

text: systems

text: using

text: a

text: slight

text: variation

text: of

text: the

text: Gauss–Jordan

text: elimination

text: algorithm,

text: prescribed

text: by

text: the

text: following

text: elementary

text: row

text: operations:

text: Row

text: exchange

text: R

text: R

text: i

text: j

text: Row

text: scaling

text: (R

text: )k

text: R

text: i

text: i

text: Row

text: linear

text: combination

text: (R

text: )k

text: (R

text: R

text: i

text: j

text: j

text: where

text: k

text: C

text: and

text: R

text: denotes

text: the

text: particular

text: constraint

text: xait

text: b

text: i

text: t<n

text: t

text: i

text: The

text: proposed

text: modiﬁed

text: row

text: operations

text: perform

text: the

text: usual

text: row

text: operations

text: prescribed

text: by

text: the

text: Gauss–Jordan

text: elimination

text: algorithm

text: on

text: the

text: logarithmic

text: version

text: of

text: the

text: constraints.

text: Proposition

text: The

text: solution

text: X

text: to

text: the

text: orthogonalization

text: constraints

text: for

text: a

text: input

text: hyper-

text: matrix

text: A

text: yields

text: a

text: non-trivial

text: orthogonal

text: hypermatrix

text: after

text: normalizing

text: of

text: the

text: rows

text: of

text: the

text: solution

text: matrix

text: X.

text: Proof

text: The

text: proof

text: follows

text: directly

text: from

text: the

text: Gaussian

text: elimination

text: procedure.

text: The

text: row

text: echelon

text: form

text: of

text: the

text: constraints

text: are

text: obtained

text: by

text: performing

text: the

text: modiﬁed

text: row

text: linear

text: combination

text: operations

text: described

text: earlier

text: in

text: order

text: to

text: put

text: the

text: logarithmic

text: version

text: of

text: the

text: constraints

text: in

text: row

text: echelon

text: form.

text: We

text: deduce

text: from

text: the

text: expression

text: in

text: row

text: echelon

text: form

text: of

text: the

text: orthogonalization

text: constraints

text: a

text: criterion

text: for

text: establishing

text: the

text: existence

text: of

text: solutions

text: in

text: terms

text: of

text: a

text: single

text: polynomial

text: in

text: the

text: entries

text: of

text: A

text: which

text: should

text: be

text: diﬀerent

text: from

text: zero

text: for

text: some

text: input.

text: This

text: condition

text: will

text: be

text: generically

text: satisﬁed,

text: thereby

text: establishing

text: the

text: desired

text: result.

text: generic

text: hypermatrix

text: is

text: one

text: whose

text: entries

text: do

text: not

text: satisfy

text: any

text: particular

text: algebraic

text: relation.

text: ##LTLine##


text: 10 ing the size ratio from q = 5 to q = 10, the larger poly- predictions of polymer ﬁeld theories, further validating mer being relatively more compactiﬁed. Moreover, the the ellipsoidal polymer model and demonstrating the im- crowding eﬀect is much stronger here, where we com- portance of polymer shape ﬂuctuations and penetrability puted ε from Eqs. (11) and (15), than in our previous for depletion interactions. Our results for shape distri- study [74], where we used lower penetration free ener- butions of crowded polymers, including asphericity and gies. Nevertheless, a model of spherical, compressible rms radius of gyration, agree closely with predictions of polymers gives yet greater contraction [73, 74], which is free-volume theory, diﬀering quantitatively only in highly attributable to the lack of freedom of a spherical polymer concentrated nanosphere dispersions. Extending our pre- to distort its shape. vious study [74], we consistently incorporated the de- Figure 6 also shows a comparison of our simulation pendence of the penetration free energy on the polymer data with predictions of free-volume theory. As with the shape and nanoparticle concentration. Furthermore, our eigenvalue distributions, the theory faithfully captures predictions for polymer shape deformations can be tested the trends in shape, size, and volume. The inset to panel against molecular simulations or density-functional the- (b) shows a further comparison with the scaling predic- ory calculations for explicit segmented-chain polymers, ∼ − tion of Odijk [81] for the radius of gyration, R φ 1/4, which may guide reﬁnement of the step-function approx- g n which is seen to be fairly consistent with our data over a imation assumed for the penetration energy proﬁle. signiﬁcant range of nanosphere concentrations. Here the The methods and results presented here lay a foun- close agreement between the input (theory) and output dation for simulating more realistic models of polymer- (simulation) values of v serves as a consistency check on nanoparticle mixtures, as well as models of polymers in p our approximation for the penetration free energy. In the quenched disordered media [129–131]. Future work will coarse-grained polymer model, for the size ratios studied focus on generalizing the model from ideal polymers to here, neither simulation nor theory indicates a sudden nonideal polymers in good solvents with excluded-volume (cid:39) collapse of an ideal coil up to volume fractions φ 0.4. interactions [101–103] characterized by shape distribu- n V. CONCLUSIONS tions of self-avoiding random walks [39, 40], analyzing crowding of real biopolymers [104–108] (e.g., speciﬁc pro- teins and RNA), and exploring inﬂuences of polymer In summary, to investigate inﬂuences of polymer shape shape ﬂuctuations on thermodynamic stability and phase and penetrability on mixtures of hard nanospheres and behavior (e.g., demixing) of bulk polymer-nanoparticle nonadsorbing homopolymers, modeled as penetrable el- mixtures. lipsoids with ﬂuctuating shapes, we developed a Monte Carlo simulation method based on polymer insertion and ACKNOWLEDGMENTS geometric overlap algorithms. We applied our method to compute depletion-induced potentials of mean force be- This work was supported by the National Science tween nanospheres and crowding-induced shape deforma- Foundation (Grant No. DMR-1106331). We thank Jan tions of ideal polymers in the protein limit. Our simula- Forsman for helpful correspondence and for sharing the tion data for pair interactions are in good agreement with data from ref. [84] plotted in Fig. 2. fxundeﬁned [1]ifx1 fnum [1]1ﬁrstoftwo fx [1]secondoftwo noop P. N. Pusey, Colloidal Suspensions, in noop Liquids, [0]secondoftworef[1]@startlink1@hrefhref[1]1@endlinkanitize@urlFreezing and Glass Transition, Les Houches session 51, [0]startlink[1]endlink[0]rl [1]href 1bib@innerbibempty Vol. 2, edited by J.-P. Hansen, D. Levesque, and J. Zinn- H. N. W. Lekkerkerker and R. Tuinier, noop Colloids and Justin (North-Holland, Amsterdam, 1991) pp. 763–931. the Depletion Interaction (Springer, Heidelberg, 2011). R. A. L. Jones, noop Soft Condensed Matter (Oxford, A. C. Balazs, T. Emrick, and T. P. Russell, noop Science Oxford, 2002). 314, 1107 (2006). M. Fuchs and K. S. Schweizer, noop J. Phys.: Con- dens. Matter 14, R239 (2002). M. E. Mackay, A. Tuteja, P. M. Duxbury, C. J. Hawker, B. Van Horn, Z. Guan, G. Chen, and R. S. Krishnan, G. J. Fleer and R. Tuinier, noop Adv. Coll. Interface noop Science 311, 1740 (2006). Sci. 143, 1 (2008). S. Asakura and F. Oosawa, noop J. Chem. Phys. 22, A. R. Denton, Eﬀective Interactions in Soft Materials, 1255 (1954). in noop Nanostructured Soft Matter: Experiment, The- ory, Simulation and Perspectives, edited by A. V. Zvelin- P. G. de Gennes, noop Scaling Concepts in Polymer dovsky (Springer, Dordrecht, 2007) pp. 395–433. Physics (Cornell, Ithaca, 1979). V. B. Tolstoguzov, noop Food Hydrocolloids 4, 429 J. Israelachvili, noop Intermolecular and Surface Forces (1991). (Academic, London, 1992). C. de Kruif and R. Tuinier, noop Food Hydrocolloids A. Vrij, noop Pure & Appl. Chem. 48, 471 (1976). 15, 555 (2001). ##LTLine## ##LTLine## ##LTLine##

text: ing

text: the

text: size

text: ratio

text: from

text: q

text: to

text: q

text: the

text: larger

text: poly-

text: predictions

text: of

text: polymer

text: ﬁeld

text: theories,

text: further

text: validating

text: mer

text: being

text: relatively

text: more

text: compactiﬁed.

text: Moreover,

text: the

text: the

text: ellipsoidal

text: polymer

text: model

text: and

text: demonstrating

text: the

text: im-

text: crowding

text: eﬀect

text: is

text: much

text: stronger

text: here,

text: where

text: we

text: com-

text: portance

text: of

text: polymer

text: shape

text: ﬂuctuations

text: and

text: penetrability

text: puted

text: ε

text: from

text: Eqs.

text: and

text: than

text: in

text: our

text: previous

text: for

text: depletion

text: interactions.

text: Our

text: results

text: for

text: shape

text: distri-

text: study

text: where

text: we

text: used

text: lower

text: penetration

text: free

text: ener-

text: butions

text: of

text: crowded

text: polymers,

text: including

text: asphericity

text: and

text: gies.

text: Nevertheless,

text: a

text: model

text: of

text: spherical,

text: compressible

text: rms

text: radius

text: of

text: gyration,

text: agree

text: closely

text: with

text: predictions

text: of

text: polymers

text: gives

text: yet

text: greater

text: contraction

text: which

text: is

text: free-volume

text: theory,

text: diﬀering

text: quantitatively

text: only

text: in

text: highly

text: attributable

text: to

text: the

text: lack

text: of

text: freedom

text: of

text: a

text: spherical

text: polymer

text: concentrated

text: nanosphere

text: dispersions.

text: Extending

text: our

text: pre-

text: to

text: distort

text: its

text: shape.

text: vious

text: study

text: we

text: consistently

text: incorporated

text: the

text: de-

text: Figure

text: also

text: shows

text: a

text: comparison

text: of

text: our

text: simulation

text: pendence

text: of

text: the

text: penetration

text: free

text: energy

text: on

text: the

text: polymer

text: data

text: with

text: predictions

text: of

text: free-volume

text: theory.

text: As

text: with

text: the

text: shape

text: and

text: nanoparticle

text: concentration.

text: Furthermore,

text: our

text: eigenvalue

text: distributions,

text: the

text: theory

text: faithfully

text: captures

text: predictions

text: for

text: polymer

text: shape

text: deformations

text: can

text: be

text: tested

text: the

text: trends

text: in

text: shape,

text: size,

text: and

text: volume.

text: The

text: inset

text: to

text: panel

text: against

text: molecular

text: simulations

text: or

text: density-functional

text: the-

text: (b)

text: shows

text: a

text: further

text: comparison

text: with

text: the

text: scaling

text: predic-

text: ory

text: calculations

text: for

text: explicit

text: segmented-chain

text: polymers,

text: tion

text: of

text: Odijk

text: for

text: the

text: radius

text: of

text: gyration,

text: R

text: φ

text: which

text: may

text: guide

text: reﬁnement

text: of

text: the

text: step-function

text: approx-

text: g

text: n

text: which

text: is

text: seen

text: to

text: be

text: fairly

text: consistent

text: with

text: our

text: data

text: over

text: a

text: imation

text: assumed

text: for

text: the

text: penetration

text: energy

text: proﬁle.

text: signiﬁcant

text: range

text: of

text: nanosphere

text: concentrations.

text: Here

text: the

text: The

text: methods

text: and

text: results

text: presented

text: here

text: lay

text: a

text: foun-

text: close

text: agreement

text: between

text: the

text: input

text: (theory)

text: and

text: output

text: dation

text: for

text: simulating

text: more

text: realistic

text: models

text: of

text: polymer-

text: (simulation)

text: values

text: of

text: v

text: serves

text: as

text: a

text: consistency

text: check

text: on

text: nanoparticle

text: mixtures,

text: as

text: well

text: as

text: models

text: of

text: polymers

text: in

text: p

text: our

text: approximation

text: for

text: the

text: penetration

text: free

text: energy.

text: In

text: the

text: quenched

text: disordered

text: media

text: Future

text: work

text: will

text: coarse-grained

text: polymer

text: model,

text: for

text: the

text: size

text: ratios

text: studied

text: focus

text: on

text: generalizing

text: the

text: model

text: from

text: ideal

text: polymers

text: to

text: here,

text: neither

text: simulation

text: nor

text: theory

text: indicates

text: a

text: sudden

text: nonideal

text: polymers

text: in

text: good

text: solvents

text: with

text: excluded-volume

text: collapse

text: of

text: an

text: ideal

text: coil

text: up

text: to

text: volume

text: fractions

text: φ

text: interactions

text: characterized

text: by

text: shape

text: distribu-

text: n

text: V.

text: CONCLUSIONS

text: tions

text: of

text: self-avoiding

text: random

text: walks

text: analyzing

text: crowding

text: of

text: real

text: biopolymers

text: (e.g.,

text: speciﬁc

text: pro-

text: teins

text: and

text: RNA),

text: and

text: exploring

text: inﬂuences

text: of

text: polymer

text: In

text: summary,

text: to

text: investigate

text: inﬂuences

text: of

text: polymer

text: shape

text: shape

text: ﬂuctuations

text: on

text: thermodynamic

text: stability

text: and

text: phase

text: and

text: penetrability

text: on

text: mixtures

text: of

text: hard

text: nanospheres

text: and

text: behavior

text: (e.g.,

text: demixing)

text: of

text: bulk

text: polymer-nanoparticle

text: nonadsorbing

text: homopolymers,

text: modeled

text: as

text: penetrable

text: el-

text: mixtures.

text: lipsoids

text: with

text: ﬂuctuating

text: shapes,

text: we

text: developed

text: a

text: Monte

text: Carlo

text: simulation

text: method

text: based

text: on

text: polymer

text: insertion

text: and

text: ACKNOWLEDGMENTS

text: geometric

text: overlap

text: algorithms.

text: We

text: applied

text: our

text: method

text: to

text: compute

text: depletion-induced

text: potentials

text: of

text: mean

text: force

text: be-

text: This

text: work

text: was

text: supported

text: by

text: the

text: National

text: Science

text: tween

text: nanospheres

text: and

text: crowding-induced

text: shape

text: deforma-

text: Foundation

text: (Grant

text: No.

text: We

text: thank

text: Jan

text: tions

text: of

text: ideal

text: polymers

text: in

text: the

text: protein

text: limit.

text: Our

text: simula-

text: Forsman

text: for

text: helpful

text: correspondence

text: and

text: for

text: sharing

text: the

text: tion

text: data

text: for

text: pair

text: interactions

text: are

text: in

text: good

text: agreement

text: with

text: data

text: from

text: ref.

text: plotted

text: in

text: Fig.

text: fxundeﬁned

text: fnum

text: fx

text: noop

text: P.

text: N.

text: Pusey,

text: Colloidal

text: Suspensions,

text: in

text: noop

text: Liquids,

text: and

text: Glass

text: Transition,

text: Les

text: Houches

text: session

text: Vol.

text: edited

text: by

text: J.-P.

text: Hansen,

text: D.

text: Levesque,

text: and

text: J.

text: Zinn-

text: H.

text: N.

text: W.

text: Lekkerkerker

text: and

text: R.

text: Tuinier,

text: noop

text: Colloids

text: and

text: Justin

text: (North-Holland,

text: Amsterdam,

text: pp.

text: the

text: Depletion

text: Interaction

text: (Springer,

text: Heidelberg,

text: R.

text: A.

text: L.

text: Jones,

text: noop

text: Soft

text: Condensed

text: Matter

text: (Oxford,

text: A.

text: C.

text: Balazs,

text: T.

text: Emrick,

text: and

text: T.

text: P.

text: Russell,

text: noop

text: Science

text: Oxford,

text: M.

text: Fuchs

text: and

text: K.

text: S.

text: Schweizer,

text: noop

text: J.

text: Phys.:

text: Con-

text: dens.

text: Matter

text: M.

text: E.

text: Mackay,

text: A.

text: Tuteja,

text: P.

text: M.

text: Duxbury,

text: C.

text: J.

text: Hawker,

text: B.

text: Van

text: Horn,

text: Z.

text: Guan,

text: G.

text: Chen,

text: and

text: R.

text: S.

text: Krishnan,

text: G.

text: J.

text: Fleer

text: and

text: R.

text: Tuinier,

text: noop

text: Adv.

text: Coll.

text: Interface

text: noop

text: Science

text: Sci.

text: S.

text: Asakura

text: and

text: F.

text: Oosawa,

text: noop

text: J.

text: Chem.

text: Phys.

text: A.

text: R.

text: Denton,

text: Eﬀective

text: Interactions

text: in

text: Soft

text: Materials,

text: in

text: noop

text: Nanostructured

text: Soft

text: Matter:

text: Experiment,

text: The-

text: ory,

text: Simulation

text: and

text: Perspectives,

text: edited

text: by

text: A.

text: V.

text: Zvelin-

text: P.

text: G.

text: de

text: Gennes,

text: noop

text: Scaling

text: Concepts

text: in

text: Polymer

text: dovsky

text: (Springer,

text: Dordrecht,

text: pp.

text: Physics

text: (Cornell,

text: Ithaca,

text: V.

text: B.

text: Tolstoguzov,

text: noop

text: Food

text: Hydrocolloids

text: J.

text: Israelachvili,

text: noop

text: Intermolecular

text: and

text: Surface

text: Forces

text: (Academic,

text: London,

text: C.

text: de

text: Kruif

text: and

text: R.

text: Tuinier,

text: noop

text: Food

text: Hydrocolloids

text: A.

text: Vrij,

text: noop

text: Pure

text: Appl.

text: Chem.

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: ∗ Randomized Aperture Imaging † Xiaopeng Peng,1 Garreth J. Ruane,1 and Grover A. Swartzlander, Jr.1, Speckled images of a binary broad band light source (600-670 nm), generated by randomized reﬂections or transmissions, were used to reconstruct a binary image by use of multi-frame blind deconvolution algorithms. Craft store glitter was used as reﬂective elements. Another experiment used perforated foil. Also reported here are numerical models that aﬀorded controlled tip-tilt and piston aberrations. These results suggest the potential importance of a poorly ﬁgured, randomly varying segmented imaging system. Keywords: multi-aperture imaging, image processing, blind deconvolution, computational imaging, image reconstruction, multi-frame image processing PACS numbers: I. INTRODUCTION FIG. 1. Random aperture imaging system having baseline D, depicting a distant light source, random elements, and a It is well known that angular resolution may be en- detector in an eﬀective focal plane. A sequence of images are hanced by use of a larger aperture. In practice, the size of recorded for diﬀerent random orientations of the elements. a monolithic aperture is limited by the cost, weight and Computational imaging methods are used to reconstruct the construction constraints[1, 2]. Even if such constrains image of the light source. can be surmounted, adaptive optics methods must be ap- plied to achieve diﬀraction limited performance[3]. Alter- natively, passive approaches that make use of computer In some respects this study is related to the random post-processing have been successfully employed[4–6]. lens imaging system[23], where a collection of random Examples, including an aperture masking system[7], and reﬂectors served as a primary camera lens. Similarly, a multi-aperture system[8] have shown great promise in the sparkle vision system[24], simpliﬁes the random lens astronomy and remote sensing[9–11],biology[12], clinical imaging system by using a lens to better focus the light. trials[13, 14], and new types of computational cameras[15– However, in these examples, the PSF was not time- 17]. In these imaging systems, the burden of hard- varying, and intensive machine learning algorithms were ware control are replaced or greatly alleviated by digi- needed to uncover the PSF. In contrast, we aimed to tal computations. Mathematical tools, such as Fourier reconstruct the time-varying PSF in a near real-time analysis[18], constrained optimization[19, 20], and Bayesian manner. inference[21] are essential in this approach. Both aper- This report is organized as follows. In Section 2 we ture masking and multi-aperture systems have demon- provide a description of a randomized complex aperture strated an improved signal-to-noise ratio of the acquired system. Two diﬀerent experimental scenarios are estab- images, a calibrated point spread function (PSF), rejec- lished in Section 3: “far ﬁeld”and “near ﬁeld”. For the tion of atmospheric noise, and closure phase measurements[22]p.urpose of comparing experimental and modeled results, However, the sparsity of apertures implies a sparse cover- we next describe in Section 4 the corresponding numer- age of spatial frequencies and loss of ﬂux. Both adaptive ical models. Both the experimental and numerical data optics and aperture masking systems attempt to improve are processed by means of the multiframe blind decon- the images obtained from a relatively well-ﬁgured optical volution scheme described in Section 5. We then report system. In this paper we address the case of an ill-ﬁgured image construction results in Section 6. Concluding re- segmented optical system that varies randomly in time. marks are provided in Section 7. To make matters worse, we assume no knowledge of the II. BASICS OF RANDOMIZED APERTURE randomly varying PSF. We ask the following the proof IMAGING of concept question: Is it possible to reconstruct a near diﬀraction-limited image from a series of recordings from An illustration of the randomized aperture scheme, such a system? shown in Fig. 1, depicts a point source (or sources) an in- ##LTFigure##

text: Randomized

label: title

text: Aperture

text: Imaging

text: Xiaopeng

label: author

text: Garreth

text: J.

text: and

text: Grover

text: A.

text: Swartzlander,

text: Speckled

label: abstract

text: images

text: of

text: a

text: binary

text: broad

text: band

text: light

text: source

text: nm),

text: generated

text: by

text: randomized

text: reﬂections

text: or

text: transmissions,

text: were

text: used

text: to

text: reconstruct

text: a

text: binary

text: image

text: by

text: use

text: of

text: multi-frame

text: blind

text: deconvolution

text: algorithms.

text: Craft

text: store

text: glitter

text: was

text: used

text: as

text: reﬂective

text: elements.

text: Another

text: experiment

text: used

text: perforated

text: foil.

text: Also

text: reported

text: here

text: are

text: numerical

text: models

text: that

text: aﬀorded

text: controlled

text: tip-tilt

text: and

text: piston

text: aberrations.

text: These

text: results

text: suggest

text: the

text: potential

text: importance

text: of

text: a

text: poorly

text: ﬁgured,

text: randomly

text: varying

text: segmented

text: imaging

text: system.

text: Keywords:

text: multi-aperture

text: imaging,

text: image

text: processing,

text: blind

text: deconvolution,

text: computational

text: imaging,

text: image

text: reconstruction,

text: multi-frame

text: image

text: processing

text: PACS

text: numbers:

text: I.

text: INTRODUCTION

text: FIG.

text: Random

text: aperture

text: imaging

text: system

text: having

text: baseline

text: D,

text: depicting

text: a

text: distant

text: light

text: source,

text: random

text: elements,

text: and

text: a

text: It

text: is

text: well

text: known

text: that

text: angular

text: resolution

text: may

text: be

text: en-

text: detector

text: in

text: an

text: eﬀective

text: focal

text: plane.

text: A

text: sequence

text: of

text: images

text: are

text: hanced

text: by

text: use

text: of

text: a

text: larger

text: aperture.

text: In

text: practice,

text: the

text: size

text: of

text: recorded

text: for

text: diﬀerent

text: random

text: orientations

text: of

text: the

text: elements.

text: a

text: monolithic

text: aperture

text: is

text: limited

text: by

text: the

text: cost,

text: weight

text: and

text: Computational

text: imaging

text: methods

text: are

text: used

text: to

text: reconstruct

text: the

text: construction

text: Even

text: if

text: such

text: constrains

text: image

text: of

text: the

text: light

text: source.

text: can

text: be

text: surmounted,

text: adaptive

text: optics

text: methods

text: must

text: be

text: ap-

text: plied

text: to

text: achieve

text: diﬀraction

text: limited

text: Alter-

text: natively,

text: passive

text: approaches

text: that

text: make

text: use

text: of

text: computer

text: In

text: some

text: respects

text: this

text: study

text: is

text: related

text: to

text: the

text: random

text: post-processing

text: have

text: been

text: successfully

text: lens

text: imaging

text: where

text: a

text: collection

text: of

text: random

text: Examples,

text: including

text: an

text: aperture

text: masking

text: and

text: reﬂectors

text: served

text: as

text: a

text: primary

text: camera

text: lens.

text: Similarly,

text: a

text: multi-aperture

text: have

text: shown

text: great

text: promise

text: in

text: the

text: sparkle

text: vision

text: simpliﬁes

text: the

text: random

text: lens

text: astronomy

text: and

text: remote

text: clinical

text: imaging

text: system

text: by

text: using

text: a

text: lens

text: to

text: better

text: focus

text: the

text: light.

text: and

text: new

text: types

text: of

text: computational

text: However,

text: in

text: these

text: examples,

text: the

text: PSF

text: was

text: not

text: time-

text: In

text: these

text: imaging

text: systems,

text: the

text: burden

text: of

text: hard-

text: varying,

text: and

text: intensive

text: machine

text: learning

text: algorithms

text: were

text: ware

text: control

text: are

text: replaced

text: or

text: greatly

text: alleviated

text: by

text: digi-

text: needed

text: to

text: uncover

text: the

text: PSF.

text: In

text: contrast,

text: we

text: aimed

text: to

text: tal

text: computations.

text: Mathematical

text: tools,

text: such

text: as

text: Fourier

text: reconstruct

text: the

text: time-varying

text: PSF

text: in

text: a

text: near

text: real-time

text: constrained

text: and

text: Bayesian

text: manner.

text: are

text: essential

text: in

text: this

text: approach.

text: Both

text: aper-

text: This

text: report

text: is

text: organized

text: as

text: follows.

text: In

text: Section

text: we

text: ture

text: masking

text: and

text: multi-aperture

text: systems

text: have

text: demon-

text: provide

text: a

text: description

text: of

text: a

text: randomized

text: complex

text: aperture

text: strated

text: an

text: improved

text: signal-to-noise

text: ratio

text: of

text: the

text: acquired

text: system.

text: Two

text: diﬀerent

text: experimental

text: scenarios

text: are

text: estab-

text: images,

text: a

text: calibrated

text: point

text: spread

text: function

text: (PSF),

text: rejec-

text: lished

text: in

text: Section

text: “far

text: ﬁeld”and

text: “near

text: ﬁeld”.

text: For

text: the

text: tion

text: of

text: atmospheric

text: noise,

text: and

text: closure

text: phase

text: of

text: comparing

text: experimental

text: and

text: modeled

text: results,

text: However,

text: the

text: sparsity

text: of

text: apertures

text: implies

text: a

text: sparse

text: cover-

text: we

text: next

text: describe

text: in

text: Section

text: the

text: corresponding

text: numer-

text: age

text: of

text: spatial

text: frequencies

text: and

text: loss

text: of

text: ﬂux.

text: Both

text: adaptive

text: ical

text: models.

text: Both

text: the

text: experimental

text: and

text: numerical

text: data

text: optics

text: and

text: aperture

text: masking

text: systems

text: attempt

text: to

text: improve

text: are

text: processed

text: by

text: means

text: of

text: the

text: multiframe

text: blind

text: decon-

text: the

text: images

text: obtained

text: from

text: a

text: relatively

text: well-ﬁgured

text: optical

text: volution

text: scheme

text: described

text: in

text: Section

text: We

text: then

text: report

text: system.

text: In

text: this

text: paper

text: we

text: address

text: the

text: case

text: of

text: an

text: ill-ﬁgured

text: image

text: construction

text: results

text: in

text: Section

text: Concluding

text: re-

text: segmented

text: optical

text: system

text: that

text: varies

text: randomly

text: in

text: time.

text: marks

text: are

text: provided

text: in

text: Section

text: To

text: make

text: matters

text: worse,

text: we

text: assume

text: no

text: knowledge

text: of

text: the

text: II.

text: BASICS

text: OF

text: RANDOMIZED

text: APERTURE

text: randomly

text: varying

text: PSF.

text: We

text: ask

text: the

text: following

text: the

text: proof

text: IMAGING

text: of

text: concept

text: question:

text: Is

text: it

text: possible

text: to

text: reconstruct

text: a

text: near

text: diﬀraction-limited

text: image

text: from

text: a

text: series

text: of

text: recordings

text: from

text: An

text: illustration

text: of

text: the

text: randomized

text: aperture

text: scheme,

text: such

text: a

text: system?

text: shown

text: in

text: Fig.

text: depicts

text: a

text: point

text: source

text: (or

text: sources)

text: an

text: in-

text: ##LTFigure##


text: 4 FIG. 4. Numerical model of the far ﬁeld scheme. (a) Sub-apertures of radius r (small circles) are distributed across the baseline × radius D = 2R on an N N grid (N = 8192). The transmitted light has a Gaussian random tip-tilt phase (with standard deviation up to 40λ/D across the diameter D = 2R), as well as a uniformly distributed piston error of up to one wave. The M = 100 non-overlapping randomly placed sub-apertures are assigned a position c = (x , y ). (b)Numerical image of a binary i i i light source at the Fourier transform plane. The image has been inverted to aid the eye. (cid:34) (cid:35) (cid:18) (cid:19) (cid:88) ≈ U(x) = M U (x) exp |x − c0|2 γ (4) whAersesufmorinpgartahxeiatlwroaylisg,hktxsou2rcπeθs0/aλre. mutually incoher- i R ent, we write the intensity in the plane of the detector i=1 as: where M is the number of sub-apertures, c = (c , c ) 0 x,0 y,0 indicates the center of the baseline, and R the radius of I(x) = |E+|2 + |E−|2 (8) the full eﬀective aperture, and γ = 100 is the power of Super-Gaussian function that deﬁnes the baseline. We further impose a non-overlapping condition to the Near Field In the near ﬁeld regime, the numerical sub-apertures: model ignores diﬀraction of the reﬂected light as it propa- gates from the aperture to the focal plane detector. That | − | (cid:54) is, we assume the characteristic diﬀraction distance is c c > 2r , i = j (5) i j s much longer than the eﬀective focal length: πr2/λ >> f. s The geometric model of near ﬁeld scheme is illustrated in Fig 5. For a single source of collimated light, we as- An example of the complex pupil function is shown in sume a beam of parallel ray aligned along the unit vector Fig 4.(a) for M = 100 sub-apertures. d . Rays incident upon the i reﬂector centered at the For two monochromatic point sources at inﬁnity hav- 0 th point c are reﬂected along the unit vector d : ing an apparent angular separation of 2θ along the x- i r,i 0 direction, the electric ﬁeld in the back focal plane of the system may be expressed as Fourier transforms of the − · d = d 2 (d n ) n (9) ﬁeld from each source, incident upon the imaging sys- r,i 0 0 i i tem(assuming it is shif(cid:18)t-invarian(cid:19)t): (cid:88) where the Cartesian components of the unit normal vec- 1 2π · tor of the ith reﬂector may be expressed in terms of direc- E+(v) = λ exp i λ v x U(x)exp(+ikxx) (6) tion cosines as: ni = (cos θi), where θi = (θx,i, θy,i, θz,i). x If the reﬂectors conformed to a paraboloid (cid:18) (cid:19) (cid:88) − z = (x2 + y2)/4f + f (10) − 1 2π · − E (v) = exp i v x U(x)exp( ik x) (7) λ λ x x ##LTFigure## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: FIG.

text: Numerical

text: model

text: of

text: the

text: far

text: ﬁeld

text: scheme.

text: (a)

text: Sub-apertures

text: of

text: radius

text: r

text: (small

text: circles)

text: are

text: distributed

text: across

text: the

text: baseline

text: radius

text: D

text: on

text: an

text: N

text: N

text: grid

text: (N

text: The

text: transmitted

text: light

text: has

text: a

text: Gaussian

text: random

text: tip-tilt

text: phase

text: (with

text: standard

text: deviation

text: up

text: to

text: across

text: the

text: diameter

text: D

text: as

text: well

text: as

text: a

text: uniformly

text: distributed

text: piston

text: error

text: of

text: up

text: to

text: one

text: wave.

text: The

text: M

text: non-overlapping

text: randomly

text: placed

text: sub-apertures

text: are

text: assigned

text: a

text: position

text: c

text: (x

text: y

text: (b)Numerical

text: image

text: of

text: a

text: binary

text: i

text: i

text: i

text: light

text: source

text: at

text: the

text: Fourier

text: transform

text: plane.

text: The

text: image

text: has

text: been

text: inverted

text: to

text: aid

text: the

text: eye.

text: U(x)

text: M

text: U

text: (x)

text: exp

text: |x

text: γ

text: mutually

text: incoher-

text: i

text: R

text: ent,

text: we

text: write

text: the

text: intensity

text: in

text: the

text: plane

text: of

text: the

text: detector

text: as:

text: where

text: M

text: is

text: the

text: number

text: of

text: sub-apertures,

text: c

text: (c

text: c

text: indicates

text: the

text: center

text: of

text: the

text: baseline,

text: and

text: R

text: the

text: radius

text: of

text: I(x)

text: the

text: full

text: eﬀective

text: aperture,

text: and

text: γ

text: is

text: the

text: power

text: of

text: Super-Gaussian

text: function

text: that

text: deﬁnes

text: the

text: baseline.

text: We

text: further

text: impose

text: a

text: non-overlapping

text: condition

text: to

text: the

text: Near

text: Field

text: In

text: the

text: near

text: ﬁeld

text: regime,

text: the

text: numerical

text: sub-apertures:

text: model

text: ignores

text: diﬀraction

text: of

text: the

text: reﬂected

text: light

text: as

text: it

text: propa-

text: gates

text: from

text: the

text: aperture

text: to

text: the

text: focal

text: plane

text: detector.

text: That

text: is,

text: we

text: assume

text: the

text: characteristic

text: diﬀraction

text: distance

text: is

text: c

text: c

text: i

text: j

text: i

text: j

text: s

text: much

text: longer

text: than

text: the

text: eﬀective

text: focal

text: length:

text: f.

text: s

text: The

text: geometric

text: model

text: of

text: near

text: ﬁeld

text: scheme

text: is

text: illustrated

text: in

text: Fig

text: For

text: a

text: single

text: source

text: of

text: collimated

text: light,

text: we

text: as-

text: An

text: example

text: of

text: the

text: complex

text: pupil

text: function

text: is

text: shown

text: in

text: sume

text: a

text: beam

text: of

text: parallel

text: ray

text: aligned

text: along

text: the

text: unit

text: vector

text: Fig

text: for

text: M

text: sub-apertures.

text: d

text: Rays

text: incident

text: upon

text: the

text: i

text: reﬂector

text: centered

text: at

text: the

text: For

text: two

text: monochromatic

text: point

text: sources

text: at

text: inﬁnity

text: hav-

text: th

text: point

text: c

text: are

text: reﬂected

text: along

text: the

text: unit

text: vector

text: d

text: ing

text: an

text: apparent

text: angular

text: separation

text: of

text: 2θ

text: along

text: the

text: x-

text: i

text: r,i

text: direction,

text: the

text: electric

text: ﬁeld

text: in

text: the

text: back

text: focal

text: plane

text: of

text: the

text: system

text: may

text: be

text: expressed

text: as

text: Fourier

text: transforms

text: of

text: the

text: d

text: d

text: (d

text: n

text: n

text: ﬁeld

text: from

text: each

text: source,

text: incident

text: upon

text: the

text: imaging

text: sys-

text: r,i

text: i

text: i

text: tem(assuming

text: it

text: is

text: where

text: the

text: Cartesian

text: components

text: of

text: the

text: unit

text: normal

text: vec-

text: 2π

text: tor

text: of

text: the

text: ith

text: reﬂector

text: may

text: be

text: expressed

text: in

text: terms

text: of

text: direc-

text: E+(v)

text: λ

text: exp

text: i

text: λ

text: v

text: x

text: U(x)exp(+ikxx)

text: tion

text: cosines

text: as:

text: ni

text: (cos

text: θi),

text: where

text: θi

text: (θx,i,

text: θy,i,

text: θz,i).

text: x

text: If

text: the

text: reﬂectors

text: conformed

text: to

text: a

text: paraboloid

text: z

text: f

text: 2π

text: E

text: (v)

text: exp

text: i

text: v

text: x

text: U(x)exp(

text: ik

text: x)

text: λ

text: λ

text: x

text: x

text: ##LTFigure##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: | unit name non-linearity f(η) Gaussian approximation conditional dist p(h η) (cid:112)− − (cid:112) { −(cid:112) } Sigmoid (Bernoulli) Unit (1 + e η) 1 - exp ηh log(1 + exp(η)) Noisy Tanh Unit (1 + e−η)(cid:112)−1 − 1 N(f(η),(f(η) − 1(cid:112)/2)(f(η) + 1/2)) exp{ηh − log(1 + exp(η)) + ent(h) − g(h)} ArcSinh Unit log(η + 1 + η22) N(sinh−1(η),( 1 + η2)−1) exp{ηh − cosh(h) + 1 + η2 − ηsin−1(η) − g(h)} | | N | | { − | | − − } Symmetric Sqrt Unit (SymSqU) sign(η) η (f(Nη), η /2) exp{ ηh− h 3/3− 2(η2)−34/3 √g(h) } Linear (Gaussian) Unit η (η,1) exp ηh 1(η2) 1(h2) log( 2π) N − − { − 2 2 − − − − } Softplus Unit log(1 + eη) N(f(η),(1I+ e η) 1) exp ηh + Li2( eη) + Li2(eh) + hlog(1 eh) hlog(eh 1) g(h) Rectiﬁed Linear Unit (ReLU) max(0,η) (f(η), (η > 0)) - | | N I Rectiﬁed Quadratic Unit (ReQU) max(0,η η ) (f(η), (η > 0)η) - | | N | | | | { − | | − − } Symmetric Quadratic Unit (SymQU) η η N(η η , η ) exp{ηh− η 3−/3 2(h2)−34/3 −g(h)} Exponential Unit eη (eη,eη) exp ηh eη √h(log(y) 1) g(h) − − N { − − − − } Sinh Unit 1(eη e η) (sinh(η),cosh(η)) exp ηh cosh(η) + 1 + h2 hsin 1(h) g(h) 2 { − − } Poisson Unit eη - exp ηh eη h! Table 1: Stochastic units, their conditional distribution (eq. (2)) and the Gaussian approximation to this distribution. · I Here Li( ) is the polylogarithmic function and (cond.) is equal to one if the condition is satisﬁed and zero otherwise. ent(p) is the binary entropy function. 2.2 The Joint Form where g is the base measure and D is the Bregman f So far we have deﬁned the conditional distribution of divergence for the function f. our Exp-RBM as members of, using a single mean pa- The Bregman divergence (Bregman, 1967; Banerjee rameter f(ηj) (or f(νi) for visible units) that repre- et al., 2005) between h and η for a monotonically sents the activation function of the neuron. Now we j j increasing transfer function (corresponding to the ac- would like to ﬁnd the corresponding joint form and the tivation function) f is given by3 energy function. The problem of relating the local conditionals to the joint form in graphical models goes back to the work (cid:107) − ∗ of Besag (1974).It is easy to check that, using the more D (η h ) = η h + F(η ) + F (h ) (3) f j j j j j j general treatment of Yang et al. (2012), the joint form corresponding to the conditional of eq. (2) is (cid:18) where F with d F(η ) = f(η ) is the anti-derivative ∗ dη j j − of f and F is the anti-derivative of f 1. Substitut- p(v(cid:88), h |(cid:0)W) = exp vT(cid:1) · W(cid:88)· h(cid:0) (cid:1) (4) (cid:19) ing this expression for Bregmann divergence in eq. (2), ∗ we notice both F and g are functions of h . In fact, j − ∗ − ∗ − these two functions are often not separated (e.g., Mc- F (v ) + g(v ) F (h ) + g(h ) A(W) i i j j Cullagh et al., 1989). By separating them we see that i j some times, g simpliﬁes to a constant, enabling us to approximate Equation (2) in ?? . where A(W) is the joint normalization constant. It − ∗ Example 2.1. Let f(η ) = η be a linear neu- is noteworthy that only the anti-derivative of f 1, F j ∗j ron. Then F(η ) = 1η2 and F (h ) = 1h2, giving appears in the joint form and F is absent. From this, j 2 j j 2 j| a Gaussian conditional distribution √p(h η ) = the energy function is j j − − e 12(hj ηj)2+g(hj), where g(hj) = log( 2π) is a con- stant. (cid:88) (cid:0) (cid:1) (cid:88) (cid:0) (cid:1) − · · E(v, h) = vT W h (5) ∗ ∗ + F (v ) + g(v ) + F (h ) + g(h ) . i i j j 3 The conventional form of Bregman divergence is (cid:107) − − − − − i j D (η h ) = F(η ) F(f 1(h )) h (η f 1(h )), f j j j j j j j where F is the anti-derivative of f. Since F is strictly co∗nvex and diﬀer(cid:104)entiab(cid:105)le−, it has a Legendre-Fenchel dual Example 2.2. For the sigmoid non-linearity Ftive(hoj)f t=he sru.phη.sj. hjw, η.rj.t. ηF(tηoj)z.eroNtoow,gesteththe= dfe(rηiva)-, f(∗ηj) = 1+e1−η−j , we have −F(ηj) = log(1 + eηj) and or−ηj = f−1(hj), where Fj∗(hj) is the anti-dejr−ivative jof F (hj) = (1 hj) log(1 ∈hj{) + h}j log(hj) is the f 1(hi). Using the d−uality to switc−h f an−d f∗ 1 in the negative entropy. Since hj 0, 1 ∗only takes ex- above we can get F(f 1(h )) = h f 1(h ) F (h ). By treme values, the negative entropy F (h ) evaluates j j j j j replacing this in the original form of Bregman divergence we get the alternative form of Equation (3). ##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## ##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: unit

text: name

text: non-linearity

text: f(η)

text: Gaussian

text: approximation

text: conditional

text: dist

text: p(h

text: η)

text: Sigmoid

text: (Bernoulli)

text: Unit

text: e

text: η)

text: exp

text: ηh

text: exp(η))

text: Noisy

text: Tanh

text: Unit

text: N(f(η),(f(η)

text: exp{ηh

text: exp(η))

text: ent(h)

text: g(h)}

text: ArcSinh

text: Unit

text: log(η

text: exp{ηh

text: cosh(h)

text: η2

text: g(h)}

text: N

text: Symmetric

text: Sqrt

text: Unit

text: (SymSqU)

text: sign(η)

text: η

text: (f(Nη),

text: η

text: exp{

text: ηh−

text: h

text: √g(h)

text: Linear

text: (Gaussian)

text: Unit

text: η

text: exp

text: ηh

text: log(

text: N

text: Softplus

text: Unit

text: eη)

text: e

text: η)

text: exp

text: ηh

text: eη)

text: eh)

text: hlog(eh

text: g(h)

text: Rectiﬁed

text: Linear

text: Unit

text: (ReLU)

text: (f(η),

text: (η

text: N

text: I

text: Rectiﬁed

text: Quadratic

text: Unit

text: (ReQU)

text: η

text: (f(η),

text: (η

text: N

text: Symmetric

text: Quadratic

text: Unit

text: (SymQU)

text: η

text: η

text: N(η

text: η

text: η

text: exp{ηh−

text: η

text: −g(h)}

text: Exponential

text: Unit

text: eη

text: (eη,eη)

text: exp

text: ηh

text: eη

text: √h(log(y)

text: g(h)

text: N

text: Sinh

text: Unit

text: e

text: η)

text: (sinh(η),cosh(η))

text: exp

text: ηh

text: cosh(η)

text: hsin

text: g(h)

text: Poisson

text: Unit

text: eη

text: exp

text: ηh

text: eη

text: h!

text: Table

text: Stochastic

text: units,

text: their

text: conditional

text: distribution

text: (eq.

text: and

text: the

text: Gaussian

text: approximation

text: to

text: this

text: distribution.

text: I

text: Here

text: Li(

text: is

text: the

text: polylogarithmic

text: function

text: and

text: (cond.)

text: is

text: equal

text: to

text: one

text: if

text: the

text: condition

text: is

text: satisﬁed

text: and

text: zero

text: otherwise.

text: ent(p)

text: is

text: the

text: binary

text: entropy

text: function.

text: The

text: Joint

text: Form

text: where

text: g

text: is

text: the

text: base

text: measure

text: and

text: D

text: is

text: the

text: Bregman

text: f

text: So

text: far

text: we

text: have

text: deﬁned

text: the

text: conditional

text: distribution

text: of

text: divergence

text: for

text: the

text: function

text: f.

text: our

text: Exp-RBM

text: as

text: members

text: of,

text: using

text: a

text: single

text: mean

text: pa-

text: The

text: Bregman

text: divergence

text: (Bregman,

text: Banerjee

text: rameter

text: f(ηj)

text: (or

text: f(νi)

text: for

text: visible

text: units)

text: that

text: repre-

text: et

text: al.,

text: between

text: h

text: and

text: η

text: for

text: a

text: monotonically

text: sents

text: the

text: activation

text: function

text: of

text: the

text: neuron.

text: Now

text: we

text: j

text: j

text: increasing

text: transfer

text: function

text: (corresponding

text: to

text: the

text: ac-

text: would

text: like

text: to

text: ﬁnd

text: the

text: corresponding

text: joint

text: form

text: and

text: the

text: tivation

text: function)

text: f

text: is

text: given

text: energy

text: function.

text: The

text: problem

text: of

text: relating

text: the

text: local

text: conditionals

text: to

text: the

text: joint

text: form

text: in

text: graphical

text: models

text: goes

text: back

text: to

text: the

text: work

text: of

text: Besag

text: is

text: easy

text: to

text: check

text: that,

text: using

text: the

text: more

text: D

text: (η

text: h

text: η

text: h

text: F(η

text: F

text: (h

text: f

text: j

text: j

text: j

text: j

text: j

text: j

text: general

text: treatment

text: of

text: Yang

text: et

text: al.

text: the

text: joint

text: form

text: corresponding

text: to

text: the

text: conditional

text: of

text: eq.

text: is

text: where

text: F

text: with

text: d

text: F(η

text: f(η

text: is

text: the

text: anti-derivative

text: dη

text: j

text: j

text: of

text: f

text: and

text: F

text: is

text: the

text: anti-derivative

text: of

text: f

text: Substitut-

text: h

text: exp

text: ing

text: this

text: expression

text: for

text: Bregmann

text: divergence

text: in

text: eq.

text: we

text: notice

text: both

text: F

text: and

text: g

text: are

text: functions

text: of

text: h

text: In

text: fact,

text: j

text: these

text: two

text: functions

text: are

text: often

text: not

text: separated

text: (e.g.,

text: Mc-

text: F

text: (v

text: g(v

text: F

text: (h

text: g(h

text: A(W)

text: i

text: i

text: j

text: j

text: Cullagh

text: et

text: al.,

text: By

text: separating

text: them

text: we

text: see

text: that

text: i

text: j

text: some

text: times,

text: g

text: simpliﬁes

text: to

text: a

text: constant,

text: enabling

text: us

text: to

text: approximate

text: Equation

text: in

text: where

text: A(W)

text: is

text: the

text: joint

text: normalization

text: constant.

text: It

text: Example

text: Let

text: f(η

text: η

text: be

text: a

text: linear

text: neu-

text: is

text: noteworthy

text: that

text: only

text: the

text: anti-derivative

text: of

text: f

text: F

text: j

text: ∗j

text: ron.

text: Then

text: F(η

text: and

text: F

text: (h

text: giving

text: appears

text: in

text: the

text: joint

text: form

text: and

text: F

text: is

text: absent.

text: From

text: this,

text: j

text: j

text: j

text: j|

text: a

text: Gaussian

text: conditional

text: distribution

text: √p(h

text: η

text: the

text: energy

text: function

text: is

text: j

text: j

text: e

text: where

text: g(hj)

text: log(

text: is

text: a

text: con-

text: stant.

text: E(v,

text: h)

text: vT

text: W

text: h

text: F

text: (v

text: g(v

text: F

text: (h

text: g(h

text: i

text: i

text: j

text: j

text: The

text: conventional

text: form

text: of

text: Bregman

text: divergence

text: is

text: i

text: j

text: D

text: (η

text: h

text: F(η

text: F(f

text: h

text: (η

text: f

text: f

text: j

text: j

text: j

text: j

text: j

text: j

text: j

text: where

text: F

text: is

text: the

text: anti-derivative

text: of

text: f.

text: Since

text: F

text: is

text: strictly

text: co∗nvex

text: and

text: it

text: has

text: a

text: Legendre-Fenchel

text: dual

text: Example

text: For

text: the

text: sigmoid

text: non-linearity

text: Ftive(hoj)f

text: t=he

text: sru.phη.sj.

text: hjw,

text: η.rj.t.

text: ηF(tηoj)z.eroNtoow,gesteththe=

text: dfe(rηiva)-,

text: f(∗ηj)

text: we

text: have

text: −F(ηj)

text: eηj)

text: and

text: or−ηj

text: where

text: Fj∗(hj)

text: is

text: the

text: anti-dejr−ivative

text: jof

text: F

text: (hj)

text: hj)

text: ∈hj{)

text: h}j

text: log(hj)

text: is

text: the

text: f

text: Using

text: the

text: d−uality

text: to

text: switc−h

text: f

text: an−d

text: f∗

text: in

text: the

text: negative

text: entropy.

text: Since

text: hj

text: ∗only

text: takes

text: ex-

text: above

text: we

text: can

text: get

text: F(f

text: h

text: f

text: F

text: (h

text: By

text: treme

text: values,

text: the

text: negative

text: entropy

text: F

text: (h

text: evaluates

text: j

text: j

text: j

text: j

text: j

text: replacing

text: this

text: in

text: the

text: original

text: form

text: of

text: Bregman

text: divergence

text: we

text: get

text: the

text: alternative

text: form

text: of

text: Equation

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: ##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: to zero: However, note that in generative training, h is not (cid:18) (cid:19) j simply equal to f(η ), but it is sampled from the expo- j nential family distribution eq. (2) with the mean f(η ) j | − − – that is h = f(η )+noise. This extends the previous j j p(h η ) = exp h η log(1 + exp(η )) g(h ) j j j j j j observations linking the discriminative and generative (6) (or regularized) training – via Gaussian noise injection – to the noise from other members of the exponential family (e.g., An, 1996; Vincent et al., 2008; Bishop, Separately evaluating this expression for h = 0 j 1995) which in turn relates to the regularizing role of and h = 1, shows that the above conditional is j generative pretraining of neural networks (Erhan et al., a well-deﬁned distribution for g(h ) = 0, and in j 2010). fact it turns out to be the sigmoid function itself | – i.e., p(hj = 1 ηj) = 1+e1−ηj . When all con- Our sampling scheme (next section) further suggests that when using output Gaussian noise injection for ditionals in the RBM are of the form eq. (6) – regularization of arbitrary activation functions, the i.e., for a binary RBM with a sigmoid non-linearity, { } { } variance of this noise should be scaled by the since F(η ) and F(ν ) do not appear in the j j(cid:0) i ∗ i (cid:1) ∗ derivative of the activation function. joint form eq. (4) and F (0) = F (1) = 0, the joint form has the· sim· pl−e and the familiar form 3.1 Sampling p(v, h) = exp vT W h A(W) . To learn the generative model, we need to be able to sample from the distributions that deﬁne the expec- tations in eq. (7). Sampling from the joint model can 3 Learning also be reduced to alternating conditional sampling of (cid:81) visible and hidden variables (i.e., block Gibbs sam- A consistent estimator for the parameters W, given D { } pling). Many methods, including contrastive diver- observations = v(1), . . . , v(N) , is obtained by | gence (CD; Hinton, 2002), stochastic maximum likeli- maximizing the marginal likelihood p(v(n) W), (cid:0) (cid:80) (cid:1) n hood (a.k.a. persistent CD Tieleman, 2008) and their where the eq. (4) deﬁnes the joint probability variations (e.g., Tieleman and Hinton, 2009; Breuleux p(v, h). The gradient of the log-marginal-likelihood ∇ | et al., 2011) only require this alternating sampling in log(p(v(n) W)) is W (cid:88)n order to optimize an approximation to the gradient of eq. (7). 1 E · − E · | | [h (v(n))T ] | [h vT ](7) Here, we are interested in sampling from p(h η ) N p(h v(n),W) p(h,v W) | j j n and p(vi νi) as deﬁned in eq. (2), which is in gen- (cid:81) eral non-trivial. However some members of the expo- where the ﬁrst expectation is w.r.t. the observed data nential family have relatively eﬃcient sampling proce- | | | in which p(h v) = p(h v) and p(h v) is given dures (Ahrens and Dieter, 1974). One of these mem- j j j by eq. (2). The second expectation is w.r.t.(cid:80)the model bers that we use in our experiments is the Poisson of eq. (4). distribution. When discriminatively training a neuron f( W v ) Example 3.1. For a Poisson unit, a Poisson dis- D { } i i,j i using input output pairs = (v(n), h(n)) , in order tribution j n to have a loss that is convex in the model parame- ters W , it is common to use a matching loss for the :j gisivseinmtprlaynstfheer fBu(cid:80)rnecgtmioannfd(iHveerlmgebnocledDetfa(fl.,(η1j(9n9)9)(cid:107)).hT(jnh)i)s, p(hj | λ) = λhhjj! e−λ (8) where η(n) = W v(n). Minimizing this match- j i(cid:0) (cid:80)i,j i (cid:1) ing loss corresponds to maximizing the log-likelihood represents the probability of a neuron ﬁring h j of eq. (2), and it should not be surprising that times in a unit of time, given its average rate is ∇ (cid:107) the gradien(cid:88)t D (f(η(n)) h(n)) of this loss λ. We can deﬁne Poisson units within Exp-RBM W:j n f j j w.r.t. W:j = [W1,j, . . . , WM,j] us∗ing fj(ηj) = eηj, −which gives F|(ηj) = eηj and − F (h ) = h (log(h ) 1). For p(h η ) to be prop- f(η(n))(v(n))T h(n)(v(n))T j j j ∈ Z j j j j erly normalized, since h + is a non-negative ∗ j ≈ ∗ n integer, F (h ) + g(h ) = log(h !) F (h ) (us- j j j j resembles that of eq. (7), where f(η(n)) above substi- j tutes h in eq. (7). j ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: to

text: zero:

text: However,

text: note

text: that

text: in

text: generative

text: training,

text: h

text: is

text: not

text: j

text: simply

text: equal

text: to

text: f(η

text: but

text: it

text: is

text: sampled

text: from

text: the

text: expo-

text: j

text: nential

text: family

text: distribution

text: eq.

text: with

text: the

text: mean

text: f(η

text: j

text: that

text: is

text: h

text: f(η

text: )+noise.

text: This

text: extends

text: the

text: previous

text: j

text: j

text: p(h

text: η

text: exp

text: h

text: η

text: exp(η

text: g(h

text: j

text: j

text: j

text: j

text: j

text: j

text: observations

text: linking

text: the

text: discriminative

text: and

text: generative

text: (or

text: regularized)

text: training

text: via

text: Gaussian

text: noise

text: injection

text: to

text: the

text: noise

text: from

text: other

text: members

text: of

text: the

text: exponential

text: family

text: (e.g.,

text: An,

text: Vincent

text: et

text: al.,

text: Bishop,

text: Separately

text: evaluating

text: this

text: expression

text: for

text: h

text: j

text: which

text: in

text: turn

text: relates

text: to

text: the

text: regularizing

text: role

text: of

text: and

text: h

text: shows

text: that

text: the

text: above

text: conditional

text: is

text: j

text: generative

text: pretraining

text: of

text: neural

text: networks

text: (Erhan

text: et

text: al.,

text: a

text: well-deﬁned

text: distribution

text: for

text: g(h

text: and

text: in

text: j

text: fact

text: it

text: turns

text: out

text: to

text: be

text: the

text: sigmoid

text: function

text: itself

text: i.e.,

text: p(hj

text: ηj)

text: When

text: all

text: con-

text: Our

text: sampling

text: scheme

text: (next

text: section)

text: further

text: suggests

text: that

text: when

text: using

text: output

text: Gaussian

text: noise

text: injection

text: for

text: ditionals

text: in

text: the

text: RBM

text: are

text: of

text: the

text: form

text: eq.

text: regularization

text: of

text: arbitrary

text: activation

text: functions,

text: the

text: i.e.,

text: for

text: a

text: binary

text: RBM

text: with

text: a

text: sigmoid

text: non-linearity,

text: variance

text: of

text: this

text: noise

text: should

text: be

text: scaled

text: by

text: the

text: since

text: F(η

text: and

text: F(ν

text: do

text: not

text: appear

text: in

text: the

text: j

text: i

text: i

text: derivative

text: of

text: the

text: activation

text: function.

text: joint

text: form

text: eq.

text: and

text: F

text: F

text: the

text: joint

text: form

text: has

text: the·

text: sim·

text: pl−e

text: and

text: the

text: familiar

text: form

text: Sampling

text: p(v,

text: h)

text: exp

text: vT

text: W

text: h

text: A(W)

text: To

text: learn

text: the

text: generative

text: model,

text: we

text: need

text: to

text: be

text: able

text: to

text: sample

text: from

text: the

text: distributions

text: that

text: deﬁne

text: the

text: expec-

text: tations

text: in

text: eq.

text: Sampling

text: from

text: the

text: joint

text: model

text: can

text: Learning

text: also

text: be

text: reduced

text: to

text: alternating

text: conditional

text: sampling

text: of

text: visible

text: and

text: hidden

text: variables

text: (i.e.,

text: block

text: Gibbs

text: sam-

text: A

text: consistent

text: estimator

text: for

text: the

text: parameters

text: W,

text: given

text: D

text: pling).

text: Many

text: methods,

text: including

text: contrastive

text: diver-

text: observations

text: v(N)

text: is

text: obtained

text: by

text: gence

text: (CD;

text: Hinton,

text: stochastic

text: maximum

text: likeli-

text: maximizing

text: the

text: marginal

text: likelihood

text: p(v(n)

text: W),

text: n

text: hood

text: (a.k.a.

text: persistent

text: CD

text: Tieleman,

text: and

text: their

text: where

text: the

text: eq.

text: deﬁnes

text: the

text: joint

text: probability

text: variations

text: (e.g.,

text: Tieleman

text: and

text: Hinton,

text: Breuleux

text: p(v,

text: h).

text: The

text: gradient

text: of

text: the

text: log-marginal-likelihood

text: et

text: al.,

text: only

text: require

text: this

text: alternating

text: sampling

text: in

text: log(p(v(n)

text: W))

text: is

text: W

text: order

text: to

text: optimize

text: an

text: approximation

text: to

text: the

text: gradient

text: of

text: eq.

text: E

text: E

text: [h

text: (v(n))T

text: [h

text: vT

text: Here,

text: we

text: are

text: interested

text: in

text: sampling

text: from

text: p(h

text: η

text: N

text: p(h

text: v(n),W)

text: p(h,v

text: W)

text: j

text: j

text: n

text: and

text: p(vi

text: νi)

text: as

text: deﬁned

text: in

text: eq.

text: which

text: is

text: in

text: gen-

text: eral

text: non-trivial.

text: However

text: some

text: members

text: of

text: the

text: expo-

text: where

text: the

text: ﬁrst

text: expectation

text: is

text: w.r.t.

text: the

text: observed

text: data

text: nential

text: family

text: have

text: relatively

text: eﬃcient

text: sampling

text: proce-

text: in

text: which

text: p(h

text: v)

text: p(h

text: v)

text: and

text: p(h

text: v)

text: is

text: given

text: dures

text: (Ahrens

text: and

text: Dieter,

text: One

text: of

text: these

text: mem-

text: j

text: j

text: j

text: by

text: eq.

text: The

text: second

text: expectation

text: is

text: model

text: bers

text: that

text: we

text: use

text: in

text: our

text: experiments

text: is

text: the

text: Poisson

text: of

text: eq.

text: distribution.

text: When

text: discriminatively

text: training

text: a

text: neuron

text: f(

text: W

text: v

text: Example

text: For

text: a

text: Poisson

text: unit,

text: a

text: Poisson

text: dis-

text: D

text: i

text: i,j

text: i

text: using

text: input

text: output

text: pairs

text: (v(n),

text: h(n))

text: in

text: order

text: tribution

text: j

text: n

text: to

text: have

text: a

text: loss

text: that

text: is

text: convex

text: in

text: the

text: model

text: parame-

text: ters

text: W

text: it

text: is

text: common

text: to

text: use

text: a

text: matching

text: loss

text: for

text: the

text: :j

text: gisivseinmtprlaynstfheer

text: p(hj

text: λ)

text: λhhjj!

text: e−λ

text: where

text: η(n)

text: W

text: v(n).

text: Minimizing

text: this

text: match-

text: j

text: i

text: ing

text: loss

text: corresponds

text: to

text: maximizing

text: the

text: log-likelihood

text: represents

text: the

text: probability

text: of

text: a

text: neuron

text: ﬁring

text: h

text: j

text: of

text: eq.

text: and

text: it

text: should

text: not

text: be

text: surprising

text: that

text: times

text: in

text: a

text: unit

text: of

text: time,

text: given

text: its

text: average

text: rate

text: is

text: the

text: D

text: (f(η(n))

text: h(n))

text: of

text: this

text: loss

text: λ.

text: We

text: can

text: deﬁne

text: Poisson

text: units

text: within

text: Exp-RBM

text: W:j

text: n

text: f

text: j

text: j

text: w.r.t.

text: W:j

text: WM,j]

text: us∗ing

text: fj(ηj)

text: eηj,

text: −which

text: gives

text: F|(ηj)

text: eηj

text: and

text: F

text: (h

text: h

text: (log(h

text: For

text: p(h

text: η

text: to

text: be

text: prop-

text: f(η(n))(v(n))T

text: h(n)(v(n))T

text: j

text: j

text: j

text: Z

text: j

text: j

text: j

text: j

text: erly

text: normalized,

text: since

text: h

text: is

text: a

text: non-negative

text: j

text: n

text: integer,

text: F

text: (h

text: g(h

text: log(h

text: F

text: (h

text: (us-

text: j

text: j

text: j

text: j

text: resembles

text: that

text: of

text: eq.

text: where

text: f(η(n))

text: above

text: substi-

text: j

text: tutes

text: h

text: in

text: eq.

text: j

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##