Scaling-up Diverse Orthogonal Convolutional Networks by a Paraunitary Framework
Authors: Jiahao Su
Wonmin Byeon
Furong Huang
Venue: ICLR 2022 Submitted (2022)
Keywords: orthogonal convolutions
adversarial robustness
spectral analysis
paraunitary systems

Abstract: Enforcing orthogonality in neural networks is an antidote for gradient vanishing/exploding problems, sensitivity to adversarial perturbation, and bounding generalization errors. However, many previous approaches are heuristic, and the orthogonality of convolutional layers is not systematically studied. Some of these designs are not exactly orthogonal, while others only consider standard convolutional layers and propose specific classes of their realizations. We propose a theoretical framework for orthogonal convolutional layers to address this problem, establishing the equivalence between diverse orthogonal convolutional layers in the spatial domain and the paraunitary systems in the spectral domain. Since a complete factorization exists for paraunitary systems, any orthogonal convolution layer can be parameterized as convolutions of spatial filters. Our framework endows high expressive power to various convolutional layers while maintaining their exact orthogonality. Furthermore, our layers are memory and computationally efficient for deep networks compared to previous designs. Our versatile framework, for the first time, enables the study of architecture designs for deep orthogonal networks, such as choices of skip connection, initialization, stride, and dilation. Consequently, we scale up orthogonal networks to deep architectures, including ResNet and ShuffleNet, substantially increasing the performance over their shallower counterparts. Finally, we show how to construct residual flows, a flow-based generative model that requires strict Lipschitzness, using our orthogonal networks.

Under review as a conference paper at ICLR 2022
SCALING-UP DIVERSE ORTHOGONAL CONVOLU- TIONAL NETWORKS BY A PARAUNITARY FRAMEWORK
Anonymous authors Paper under double-blind review
ABSTRACT
Enforcing orthogonality in convolutional neural networks is antidote for gra- dient vanishing/epplddngg problems, sensitivity to perturbation, and bounding generalization errors. Many previous approaches for orthogonal convolutions enforce orthogonality on its flattened kernel, which, however, do not lead to the orthogonality of the operation. Some recent approaches consider orthogonality for standard convolutional layers and propose specific classes of their realizations. In this work, we propose theoretical framework that establishes the equivalence between diverse orthogonal convolutional layers in the spatial domain and the paraunitary systems in the spectral domain. Since ID paraunitary systems admit complete factorization, we can parameterize any separable orthogonal convolu- tion as a composition of spatial filters. As a result, our framework endows high expressive power various convolutional layers while maintaining their exact orthogonality. Furthermore, our layers are memory and computationally efficient for deep networks compared previous designs. Our versatile framework, for the first time, enables the study of architectural designs for deep orthogonal networks, such as choices of skip connection, initialization, stride, and dilation. Consequently, we scale up orthogonal networks to deep architectures, including ResNet and Shuf- fleNet, substantially outperforming their shallower counterparts. Finally, we show how to construct residual flows, flow-based generative model that requires strict Lipschitzness, using our orthogonal networks.
INTRODUCTION
Convolutional neural networks (CNNs), whose deployment has witnessed extensive empirical success, still exhibit a range of limitations that are not thoroughly studied. Firstly, deep convolutional networks are in general difficult to learn, and their high performance heavily relies on techniques that are not fully understood, such as skip-connections (He et al., 20 2016a), batch normalization (loffe & Szegedy, 2015), specialized initialization (Glorot & Bengio, 2010). Secondly, they notoriously sensitive to imperceptible perturbations, including adversarial attacks (Goodfellow et al., 2014) or geometric transformations (Azulay & Weiss, 2019). Finally, precise characterization of their generalization property is still under active investigation (Neyshabur et al., 2018; Jia et al., 2019).
Orthogonal networks, which have "flat" spectrum with all singular values of the layer being 1 (each layer's 's output norm |/y|| equals its input norm ||=||, Væ), alleviate all problems above. As shown in recent works, by enforcing orthogonality in neural nets, we obtain (1) easier optimization (Zhang et al., 2018a; Qi et al., 2020); since each orthogonal layer preserves the gradient norm during backpropagation, an orthogonal network is free from gradient vanishing/ exploding problems; (2) robustness againsl adversarial perturbation (Anil et al., 2019; Li et al., 2019b; Trockman & Kolter, 2021): since each orthogonal layer is 1-Lipschitz, an orthogonal network can not amplify any perturbation to the input to flip the output prediction; (3) better generalizability as proved in (Jia et al., 2019); a network's generalization error is positively related to the standard deviation of each linear layer's singular values, thus encouraging orthogonality in the network lowers its generalization error.
Despite the benefits, enforcing orthogonality in convolutional networks is challenging. To avoid the strict constraint. orthogonal initialization (dynamical isometry) (Pennington et al., 2017; Xiao et al., 2018) and orthogonal regularization (Wang et al., 2019; Qi et al., 2020) are adopted to address the gradient vanishing/exploding problems. However, these methods are not suitable for applications that

---

Under review as a conference paper at ICLR 2022
require strict Lipschitzness, such as adversarial robustness (Anil et al., 2019) and residual flows (Chen et al., 2019), as they do not enforce strict orthogonality (and Lipschitzness) during training.
Our goal is to enforce exact orthogonality in state-of-the-ar convolutional networks without expensive computations. We identify three main challenges in doing so. Challenge I: Achieving exact orthog- onality throughout the training process. Prior works such as orthogonal regularization (Wang et al., 2019) and reshaped kernel orthogonality (Jia et al., 2017; Cisse et al., 2017), while enjoying algorithmic simplicity, do not meet the requirement of exact orthogonality. Note that enforeing orthogonality during training is necessary as a post-training orthogonalization of the weights can ruin the performance. Challenge II: Avoiding expensive computations. An efficient algorithm is crucial for scalability to large networks. Existing work based on projected gradient descent (Sedghi et al., 2019), however, requires expensive projection after each update. For instance, the projection step in Sedghi et al. (2019) computes an SVD and flattens the spectrum to enforce orthogonality. which costs (fsizoffeature) - channels") for a convolutional layer. Challenge III: Scaling-up to state-of-the-arr deep convolutional networks. There are many variants to the standard convolu- tional layer, including dilated, strided, group convolutions, which are essential for state-of-the-art deep convolutional networks. However, none of the existing methods proposes mechanisms to orthogonalize these variants. The lack of techniques, as result, limits the broad applications of orthogonal convolutional layers to state-of-the- deeper convolutional networks.
We resolve challenges I, 11, and III by proposing complete parameterizations for orthogonal ID- convolutions and separable orthogonal 2D-convolutions. First, using the convolution theorem (Op- penheim et al., 1996) (convolution in the spatial domain is equivalent to multiplication in the spectral domain), we reduce the problem of designing orthogonal convolutions to constructing unitary ma- trices for all frequencies, i.e., paraunitary system (Vaidyanathan, 1993). Therefore, we obtain parameterization for all separable orthogonal 2ID-convolutions, guaranteeing exact orthogonality and high expressive power, Note that there no previous approach that achieves exact orthogonality (up to machine precision). For the first time, our versatile framework enables the study in the designs of deep orthogonal networks, such as skip connection, initialization, stride, and dilation. Consequently, we scale orthogonal networks to deep architectures, including ResNet and ShuffleNet, substantially outperforming their shallower counterparts. Our proposed method serves as gaining insight into the trade-off' between orthogonality and expressiveness. We observe that exact orthogonality is essential in these deeper architectures with more than 10 layers (detailed discussion of exact orthogonality in Appendix E.3). Finally, we show how to deploy orthogonal networks in Residual Flow (Chen et al., 2019), a flow- generative model that requires strict Lipschitzness (Appendix F).
Summary of Contributions:
1. We establish the equivalence between orthogonal convolutions in the spatial domain and paraunitary systems in the spectral domain. Consequently, convolutions as implicit designs of paraunitary systems.
interpret existing approaches for orthogonal
2. Based on complete factorization of ID paraunitary systems, we propose the first exact and complete design for orthogonal I ID-convolutions as well as separable orthogonal 2D-convolutions, ensuring exact orthogonality and high expressive power. None of the existing works achieve a complete parameterization of all orthogonal 2D-convolutions.
3. We prove that orthogonality for various convolutional layers (strided, dilated, group) are also entirely characterized by paraunitary systems. Consequently, our design easily extends to these variants, ensuring both completeness and exactness of the orthogonal convolutions.
4. We study the design considerations for orthogonal networks (choices of skip connection, initializa- tion, depth, width, and kernel size), and show that orthogonal networks can scale to deep architectures including ResNet, WideResNet, and ShuffleNet.
ORTHOGONAL CONVOLUTIONS VIA PARAUNITARY SYSTEMS
Designing orthogonal convolutional layer (hr,s : ye he, * xx )=1. (8, index input/output channels) in the spatial domain is challenging. When a convolution layer is written as a vetrix-vector product, where the matrix is block-circulant and its (t, s)th takes a circulant form Cir (hr,,) as:
he,a hr. [2]
he [r,
h
[N]
Cir (Ir.a)
E NXN
(2.1)
[N]
12
[1]
2

---

Under review as a conference paper at ICLR 2022
Therefore, the layer is orthogonal if the block-circulant matrix [Cir (he,,) Mr= is orthogonal. However, it is not obvious how to enforce orthogonality in a block-circulant matrix.
2.1 ACHIEVING ORTHOGONAL CONVOLUTIONS BY PARAUNITARY SYSTEMS
We propose a novel design of orthogonal convolutions from spectral domain perspective, motivated by the convolution theorem (Theorem 2.1). For simplicity, we group the entries at the same locations into a vector/matrix, c.g., we denote
as æ[n] E R and a [ml] as h[n] E R Theorem 2.1 (Convolution theorem (Oppenheim et al., 1996)). For standard convolution layer h: y/1] En, h h/nnzzl ra], the convolution in the spatial domain is equivalent to a matrix- vector multiplication in the spectral domain, i.e., (z) = (2)) E C. Here, ((z)=
En= =[n]==" Y(=) = En=o y|n]=-", H(z) = - h|m]= denote the z-transforms of imput, output, kernel respectively, where N is the length of x. y and [-L, L is the span of the filter h.
The convolution theorem states that a standard convolution layer is a matrix-vector multiplication in e/ع for all frequencies
the spectral domain. As long as the transfer matrix (=) is unitary
Ve E IR (j is the imaginary unit), the convolutional layer h is orthogonal.
Therefore, major novelty of our paper, we design orthogonal convolutions through designing unitary transfer matrix (ell) ) at all frequencies w E RR which is known as a paraunitary sys- tems (Vaidyanathan, 1993; Strang & Nguyen, 1996). We prove in Theorem B.5 that convolutional layer is orthogonal in the spatial domain if and only if it is paraunitary in the spectral domain.
Benefits through paraunitary systems. (1) The spectral representation simplifies the designs of orthogonal convolutions and avoids the analysis of plock-circulant structure. (2) Since paraunitary
systems are necessary and sufficient for orthogonal convolutions, it is impossible find an orthogonal convolution whose transfer matrix is not paraunitary. (3) There exists complete factorization of paraunitary systems: any paraunitary (=) can be realized through multiplications in the spectral domain, as will show in Equation (2.2a). (4) Since multiplications in spectral domain correspond to convolutions in spatial domain, any orthogonal convolution can be realized as cascaded convolutions of multiple sub-layers, each parameterized by orthogonal matrix. (5) There are mature methods that represent orthogonal matrices via unconstrained parameters. Consequently, we can learn orthogonal convolutions using standard optimizers on model parameterized via our design.
Interpretation of existing methods. Since paraunitary system is a necessary and sufficient condition for orthogonal convolution, all existing approaches, including singular value clipping and masking (SVCM) (Sedghi et al., 2019), block convolution orthogonal parameterization (BCOP) (Li et al., 2019b), Cayley Convolution (CayleyConv) (Trockman & Kolter, 2021), skew orthogonal convolution (SOC) design paraunitary systems implicitly. We discuss these interpretations in Appendix C.3.3, and show that our SC-Fac has the lowest computational complexity among all approaches.
2.2 REALIZING PARAUNITARY SYSTEMS VIA RE-PARAMETERIZATION
After reducing the problem of orthogonal convolutions to paraunitary systems, we are left with the question of how to realize paraunitary systems. We use complete factorization form of paraunitary systems to realize any paraunitary systems. According to Theorem C.7, any paraunitary system H (=) can be written as the form in Equation (2.2a) and any H()) in this form is paraunitary system:
H(=) ((=; ((; QU ( V(=",; -. 1000(00))) 2,
(2.2a)
where V(z;
(1-
.J..
(2.2b)
Here Q is an orthogonal matrix and each (+)) is column-orthogone matrix whose number of columns is sampled uniformly from {I..... .T.. As multiplications in the spectral domain are equivalent to convolutions in the spatial domain, this complete spectral factorization of paraunitary systems in Equation (2.2a) allows us to parameterize any orthogonal convolution the spatial domain as cascaded convolutions of V(2; UO'sss spatial counterparts and the orthogonal matrix Q.
Model design in the spatial domain. We obtain a complete design of orthogonal ID-comvolutions: using learnable (column) (actamm)--rthaee -orthogonal matrices ([=())==' - -: Q. (U(()))))) we parameterize a size (L + I. + 1) convolution as cascaded convolutions of the following filters in the spatial domain
{[t - -U 110 2-- Q, {LUOOO ,I- --000 D'2
(2.3)
3

---

Under review as a conference paper at ICLR 2022
Figure provides visualization of our proposed design of orthogonal convolution layers; each block denotes a convolution and the form the filter is displayed in each of the block. In practice, we compose all (L L 1) filters into one for orthogonal convolution, which not only increases the computational parallelism but also avoids storing intermediate outputs between filters.
x
( [
U ( (1"))
( ( 1 U-U "(U "11
1 Meeaa --t (u!
Figure I: Complete design of orthogonal convolutional layer as a cascade of convolutions, whose filter coefficients are depicted each block. The matrix orthogonal and U (9's are column-orthogee
Using this ID-convolution, we obtain a complete design for separable orthogonal 2D-covollutions, which can be represented convolution of two orthogonal 1D ID-convolutional layers. With separabil- ity, we obtain a design orthogonal 2D-convolutions by composing two complete designs of orthogo- nal ID-convolutions. As result, we can parameterize separable orthogonal 2D-convolution with filter size (Li + +)) (L2+ La + 1) as a convolution of two orthogonal I ID-convolutions with learnable (ollumn-Jorthogondl matrices ((U(") 17- Q1, ( 1221) and ((U!") ) -E= Q2, (U L )22))
With a complete factorization of paraunitary systems (ID and separable 2D), we reduce the problem of designing orthogonal convolutions the one for orthogonal matrices.
Parameterization for orthogonal matrices. In Appendix C.4, we perform a comparative study on different parameterizations of orthogonal matrices, including the Björck orthogonalization (Anil et al., 2019; Li et al., 2019b), the Cayley transform (Helfrich et al., 2018; Maduranga et al., 2019), and the exponential map (Lezcano- Casado & Martinez-Rubio, 2019). In our implementation, adopt a modified exponential map due to its efficiency, exactness, and completeness. The exponential map is surjective mapping from a skew-symmetry matrix A special orthogonal matrix U (i.e.. det(U) 1) with U = exp( A) = I A + A2/2 /2 + ...,, where the infinite series is computed up to machine- preccisionn (Higham, 2009). To parameterize all orthogonal matrices, we introduce an additional orthogonal matrix Q in U Q exp( A), where Q is (randomly) generated at initialization and fixed during training (Lezcano Casado, 2019).
Now we have an end-to-end pipeline for orthogonal convolutions as shown in Figure (See Algorithm in Appendix E for a pseudo implementation). Since our method relies on separability and complete factorization for ID paraunitary systems, we call it Separable Complete Factorization (SC-Fac).
Ortho. Conv.
[=)== M"n=="
Paraunitary
[(=== ((2)
Ortho. Factors
@ @=
Model Params. A
[nx]]
e
Figure 2: SC-Fac: A pipeline for designing orthogonal convolutional layer. (1) An orthogonal convolution h[n] is equivalent paraumitary system (2) in the spectral domain (Theorem 2.1). (2) The paraunitary system (2) is multiplications factors characterized by (column-Jorthogona ma-
trices (())))=) Q, (U(O] (Equation (2.2a), Theorem B.5). (3) These orthogonal matrices parameterized by skew kkem-symmettic matrices using exponential map.
UNIPYING ORTHOGONAL CONVOLUTIONS VARIANTS
Various convolutional layers (strided, dilated, and group convolution) are widely used in neural networks. However, it is not apparent how to enforce their orthogonality, the convolution theorem (Theorem 2.1) only holds for standard convolutions. Previous approaches only deal with standard convolutions (Sedghi et al., 2019; Li et al., 2019b; Trockman & Kolter, 2021), thus orthogonality for state-of-the-aan architectures has never been studied before.
We address this limitation by modifying convolution theorem for each variant of convolution layer, which allows us to design these variants using paraunitary systems.
Theorem 3.1 (Convolution and paraunitary theorems for various convolutions). Strided, dilated, and group convolutions can be unified in the spectral domain as Y(z) = H(())(z), where Y(2), H(2), X (z) are modified Z-transforms of y. h, We instantiate H (2) for strided convolutions in Proposition C.4, dilated convolution in Proposition C.5, and group convolution in Proposition C.6.
Furthermore, a convolution is orthogonal if and only if H(z)
(z) is paraunitary.
4

---

Under review as a conference paper at ICLR 2022
In Table 1, we formulate strided, di- lated, and group convolutions in the spatial domain, interpreting them as up-sampled or down-sampled variants of a standard convolution. Now, introduce the concept of up-sampling and nown-ssmpling precisely below.
xx]
Given a sequence x, we introduce its up-sampled sequence x R with sam- pling rate R as [m] A x////R) R] for = 0 (mod R). On the other hand, its (r, Plpollyheee component x 1 indicates the r-th down-sampled se- quence with sampling rate R. defined as x 1 [n] _ x ann + r]. We illustrated an example of x and x" in Figure 3 when sampling rate R = 2. The Z-transforms of tt - are denoted as Xt#(2), x (()) respectively. Their relations (2) are studied in Appendix C.I.
(a) Up-sample
(b) nown-sample
Figure 3: Up and down sampling, In (a), the sequence x (n]] is
up sampled into x [n]. In (b), xxn]] down- samp-ed into x [ with even entries (red) and 2=1 [n] with odd entries(blue).
Table 1: Variants of convolutions. We present the modified Z-transforms, Y(2), H()), and (()) for each convolution such Y()) = X()) holds. In the table, x (x) _ [X 1
x "T
(=) = [X - (z), ................................ x x (R-1) For group convolution, h the filter for the g group with H being its Z-transform, and blkdiag (-) stacks multiple matrices into block-diagonal matrix.
Spectral Representation
Convolution Type
Spatial Representation
Y(2)
H(2)
X(=)
Standard
vi1 Σ nez hin]aaji m]
Y(2)
H(=)
X(2)
R-Dilated
1 Σ Enez h [m]]ii n]
(2)
H(*
X(=)
1. /R--Strided
y|1 = Ener [t[n]=[[ii n]
Y(2)
H
(2)
1 R-Sttrided
y Enez hln]a=1Rli n]
(()
X(s)
G-Group
y/1 = nezz blkdiag (1h2 [x]))=[( ml
Y())
blkdiag ({H)(=)))
X(:)
Now ready to interpret convolution variants. (1) Strided convolution is used adjust the feature resolution: a strided convolution (4 (-sttiiddd) decreases the resolution by down-sampling after a standard convolution, while transposed strided convolutional layer (t R-strided) increases the resolution by up-sampling before a standard convolution. (2) Dilated convolution increases the receptive field of a convolution without extra parameters: an R-dilated convolution up-samples its filters before convolution with the input. (3) Group convolution reduces the parameters and compu- tations, thus widely used by efficient architectures: a G-group convolution divides the input/output channels into G groups and restricts the connections within each group. In Appendix C.2, we prove that a convolution orthogonal if and only if its modified Z-transform (=) is paraunitary.
4 LEARNING DEEP ORTHOGONAL NETWORKS WITH LIPSCHITZ BOUNDS
In this section, switch our focus from layer design network design. In particular, aim to study how to scale-up deep orthogonal networks with Lipschitz bounds.
Lipschitz networks (Anil et al., 2019; Li et al., 2019b; Trockman & Kolter, 2021), whose Lipschitz bounds are imposed by their architectures, are proposed as competitive candidates to guarantee robustness in deep learning. A Lipschitz network consists of orthogonal layers and GroupSort activations (Anil et al., 2019) - both are 1-Lipschitz and gradient norm preserving, See Appendix D for more discussions constant L, a Lipschitz network f can compute a certified radius for each input from its output margin. Formally, denote the output margin of an input with label c as
the properties of GroupSort and Lipschitz networks. Given Lipschitz
Mx(x) e max(0, f(x). max f(x):) ief
(4.1)
i.e., the difference between the correct logit and the second largest logit. Then the output is robust to perturbation such that fxx E) f()) c, Ve ||e|| < (x) 2T..
5

---

Under review as a conference paper at ICLR 2022
Despite the benefit, existing architectures for Lipschitz networks remain simple and shallow, and Lipschitz network is typically an interleaving cascade of orthogonal layers and GroupSort activa- tions (Li ct al., 2019b). More advanced architectures, such ResNet and ShuffleNet, are still out of reach. While orthogonal layers supposedly substitute the role of batch normalization (Pennington et al., 2017; Xiao et al., 2018; Qi et al., 2020), other critical factors, including skip-connections (He et al., 2016);b) and proper initialization (Glorot & Bengio, 2010) are lacking. In this section, we explore skip-connections and initialization methods toward addressing this problem.
Skip-connections. Two general types of skip-connections are widely used in deep networks, one based on addition and another on concatenation. The addition-basse connection is proposed in ResNet (He et al., 2016a), and adopted in SE-Net (Hu et al., 2018) and EffcientNet (Tan & Le, 2019). The concatenation-based connection is proposed in flow-based generative models (Dinh et al., 2014; 2016; Kingma & Dhariwal, 2018), and adopted in DenseNet (Huang et al., 2017) and ShuffleNet (Zhang et al., 2018b; Ma et al., 2018). In what follows, we propose Lipschitz skip-connections with these two mechanisms, illustrated in Figure 6 (in Appendix D).
Proposition 4.1 (Lipschitzness of residual blocks). Suppose f f² are L-Lipschitz (for resid- ual/shortcut branches) and a E [0,1] is a learnable scalar, then an additive residual block (ar) ) is L-Lipschitz. Alternatieel,, suppose g', gg are L-Lipschitz and P is a channel permutation, then a concatenative residual block g g(x) & P p[g (x²);; g²=²)())))))) is L- Lipschitz, where [+3-] denotes channel concatenation, and x is split into 2 and x2. i.e. x = [x] D2).
I: T(a())== 2
Initialization. Proper initialization is crucial in training deep networks (Glorot & Bengio, 2010; He et al., 2016 Various methods are proposed to initialize orthogonal matrices, including the identical/perruuatiinn and torus initialization in the context of orthogonal RNNs (Henaff et al., 2016; Helfrich et al., 2018; Lezcano-Casse & CartinezzRubboo 2019). However, initialization of orthogonal convolutions was not systematically studied, and all previous approaches inherit the initialization from the underlying parameterization (Li et al., 2019b; Trockman & Kolter, 2021). In Proposition D.I, we study the condition when a paraunitary system (represented Equation (2.2a)) reduces to orthogonal matrix. This reduction allows us to apply the initialization methods for orthogonal matrices (e.g., uniform, torus) to orthogonal convolutions.
In the experiments, we will evaluate the impact of different choices of skip-comnections and initializa- tion methods to the performance of deep Lipschitz networks.
5 RELATED WORK
Dynamical isometry (Pennington et al., 2017; 2018; Chen et al., 2018; Pennington et al., 2018) aims to address the gradient vanishing/exploding problems in deep vanilla networks with orthogona initialization. These works focus on understanding the interplay between initialization and various nonlinear activations. However, these approaches do not guarantee Lipschitzness after training, thus are unsuitable for applications that require strict characterization of Lipschitz constants, such as adversarial robustness (Anil et al., 2019) and residual flows (Behrmann et al., 2019).
Learning orthogonality has three typical approaches: regularization. parameterization (representing the feasible set with unconstrained parameters), and projected gradient descent (PGD) / Riemannian gradient descent (RGD). While regularization is approximate, the latter two learn exact orthog- onality. (1) For orthogonal matrices, various regularizations are proposed in Xie et al. (2017); Bansal et al. (2018). Alternatively, numerous parameterizations exist, including Householder reflec- tions (Mhammedi et al., 2017), Given rotations (Dorobantu et al., 2016), Cayley transform (Helfrich et al., 2018), matrix exponential (Lezcano-Casall Casado & Martinez-Rubio, 2019), and algorithmic un- rolling (Anil et al., 2019; Huang et al., 2020). Lastly, Jia et al. (2017) propose PGD via singular value clipping, and Vorontsov et al. (2017); Li et al. (2019a) consider RGD. (2) For orthogonal convolutions, some existing works learn orthogonality for the flattened matrix (Jia et al., 2017; Cisse et al., 2017; Bansal et al., 2018) or each output channel (Liu et al., 2021). However, these methods do not lead to orthogonality (norm preserving) of the operation. Sedghi et al. (2019) propose to use PGD via singular value clipping and masking, which is expensive and can result in inexact orthogonality. Recent works adopt parameterizations, using block convolutions (Li et al., 2019b), Cayley transform (Trockman & Kolter, 2021), or convolution exponential (Singla & Feizi, 2021). Note that nenwork deconvolution (Ye ct al., 2020) aims to whiten the activations (i.e., orthogonalize their distribution), but the added whitening operations do not necessarily preserve orthogonality.

---

Under review as a conference paper at ICLR 2022
Paraunitary systems are extensively studied in filter banks and wavelets (Vaidyanathan, 1993; Strang & Nguyen, 1996; Lin & Vaidyanathan, 1996). Classic theory shows that 1 DD-paraunitary systems are fully characterized by spectral factorization (see Chapter 14 of Vaidyanathan (1993)), but not all MD-paraunitary systems admit a factorized form (see Chapter 8 of Lin & Vaidyanathan (1996)). While the complete characterization of MID-paraunitary systems is known in theory (which incurs difficult problem of solving a system of nonlinear equations) (Venkataraman & Levy, 1995; Zhou, 2005), most practical constructions use separable paraunitary systems (Lin & Vaidyanathan, 1996) and special classes of non-separable paraunitary systems (Hurley & Hurley, 2012). The equivalence between orthogonal convolutions and paraunitary systems thus opens the opportumities to apply these classic theories in designing orthogonal convolutions.
EXPERIMENTS
In the experiments, we achieve the following goals. (1) We demonstrate in Section 6.1 that our separable complete factorization (SC-Fae) achieves precise orthogonality (up to machine- prreciiie-riiioon).... resulting in more accurate orthogonal designs than previous ones (Sedghi et al., 2019; Li et al., 2019b; Trockman & Kolter, 2021). (2) Despite the differences in preciseness, we show in Section 6.2 that different realizations of paraunitary systems only have minor impact on the adversarial robustness of Lipschitz networks. (3) Due to the versatility of our convolutional layers and architectures, in Section 6.3, explore the best strategy to scale Lipschitz networks wider/deeper architectures. (4) In Appendix F, we further demonstrate in a successful application of orthogonal convolutions in residual flows (Chen et al., 2019). Training details are provided in Appendix F.
6.1 EXACT ORTHOGONALITY
We evaluate the orthogonality of our SC-Fac layer verse previous approaches, including Cayley- Conv (Trockman & Kolter, 2021), BCOP (Li et al., 2019b), SVCM (Sedghi et al., 2019), RKO (Cisse et al., 2017). OSSN (Miyato et al., 2018), Our experiments are based input channels and 16 x 16 input size. We orthogonalize the layer using each approach, and evaluate it with Gaussian inputs. For our SC-Fac layer, We initialize all orthogonal matrices uniformly, while we use built-in initialization for others. We evaluate the difference between and the ratio of the output norm the input norm a layer is exactly orthogonal if the number is close to 0.
convolutional layer with 64
Table 2: (Left) Orthogonality evaluation of different designs for standard convolution. The number [[Cov(zz)]/|||]] - indicates the difference hetween the output and input norms of layer. A layer is more precisely orthogonal if the number is closer to O. As shown, SC-Fac achieves orders of magnitude orthogonal on standard convolution. (Right) Orthogonality evaluation our SC-Fac design for various convolutions. The numbers |[onnvæ)) |||||| displayed are in the magnitude of 10 - As shown, our SC-Fac achieves machine epsilon orthogonality on variants of convolution.
Conv.
| [Colla=)]l||
Groups
Type
SC-Fac
(43.14 1 7.38) 10
+3.14 7.38
+1.91 6.87
+1.44
6.29
CayleyConv
(+2.88 1 1.90) x 10-4
R-Dilated
+3.65 7.87
+1.41
11.11600 6.77
+1.02
+ 6.46
BCOP
(+2.59 1 6.14) 10-3
+3.18 7.46
+1.79 6.87
41.54 6.21
SVCM
-0.429 1 3.31 x 10-3
4. Striddd
-4.69 1
+4.38
6
+1.79
+ 5.78
RKO
OSSN
-0.666 + 1.74 x 10-3
0.442 1 3.44 x 10
1 StStrided
2
+10.39=5.15
+3.67 1: 7.96
+3.86 7.09
+1.12
+1.38 = 6.70
6.04
= 6.81
+1.43
+3.05
N/A
+ 5.79
1 6.23
(1) Standard convolution. We show in Table 2 (Left) that SC-Fac is orders of magnitude more precise than all other approaches. The SC-Fac layer is in fact exactly orthogonal up to machine epsilon, which is 2 2-24 R3 5.96 10-8 for 32-bits floats. While RKO and OSSN are known not to be orthogonal, we surprisingly find that SVCM is far from orthogonal due to its masking step. (2) Convolutions variants. In Section 3, we show that various orthogonal convolutions can be constructed using paraunitary systems. We verify our theory in Table 2 (Right): our SC-Fac layers are exactly orthogonal (up to machine precision) for various convolutions.
6.2 ADVERSARIAL ROBUSTNESS
In this subsection, evaluate the adversarial robustness of Lipschitz networks. Following the setup in (Trockman & Kolter, 1021), we adopt KW-Large, ResNet9, WideResNet1O-- 10 as the backbone architectures, and evaluate their robust accuracy on CIFAR-10 with different designs of orthogonal
7

---

Under review as a conference paper at ICLR 2022
convolutions. We extensively perform prper-paraeeter search and choose the best cyyper-paramert for each approach based on the robust accuracy. The details of the hyper- syper-parameter search is in Appendix E. We run each model with 5 different seeds and report the best accuracy.
(1) Certified robusiness. Following Li et al. (2019b), we use the raw images (without normalization) for network input to achieve the best certified aceuracy. As shown in Table 3 (Top), different realizations of paraunitary systems, SC-Fac, CayleyConv and BCOP achieve comparable performance CayleyConv performs < 1% better in clean accuracy, but the difference in robust accuracy are negligible. (2) Practical robustness. Trockman & Kolter (2021) shows that the certified accuracy is too conservative, and is possible to increase the practical robustness (against PGD attacks) with a standard input normalization. Notice that the normalization increases the Lipschitz bound, thus lower the certified accuracy. Our experiments in Table 3 (Bottom) are based on ResNet9, WideResNet100 10 (Trockman & Kolter, 2021) and deeper WideResNer22 For the shallow architectures (ResNet9, WideResNet1O-- 10-et100000000 10), our SC-Fac, CayleyConv, and BCOP again achieve comparable performance CayleyConv is slightly ahead in robust accuracy. For the deeper architecture, our SC-Fac has clear advantage in both clean and robustness accuracy, and the clean accuracy to only 5% lower than traditional ResNet 32 trained with batch normalization. Surprisingly, performs well in robust accuracy while not exactly orthogonal. In summary, our experiments show that various paraunitary realizations provide different impacts on certified and practical robustness. While exact orthogonality provides tight Lipschitz bound, there is a trade-off between the exact orthogonality and the practical robustness (especially with the shallow architectures).
find that RKO also
Table 3: (Top) Certified robustness for plain convolutional networks (without input normalization). We use KW- Large introduced by Wong et al. (2018). The results for RKO, OSSN, and SVCM are produced by Trockman & Kolter (2021). (Bottom) Practical robustness for residual networks (with input normalization). For 22 layers, the width of SC-Fac is multiplied with 10, CayleyConv with 6, and BCOP and RKO with 8. We are unable to scale CayleyConv, BCOP, and RKO due to memory constraint. As shown, deeper architectures perform better than shallow ones for all orthogonal convolution types, and our SC-Fac has clear adaattgge.
KW-Laarge
Test Acc.
SC-Fac CayleyCony
BCOP
RKO
OSSN
SVCM
Cleam
74.69
75.57
74.81
74.47
71.69
72.43
Cortified
$8.68
59.03
58.83
57,50
55.71
52.11
PGD
67.72
67.78
67.47
68.32
65.13
66.43
ResNet9
WideResNet10-UU 10
WideResNe122-noe -max
Test Acc. SC-Fac
CayleyConv BCOP
RKO
SC-Fac
CayleyConv BCOP
RKO SC-Fac
CayleyConv BCOP
RKO
Clean
82.19
84,26
83,20
84.07
84.09
82.99
84.29
84.51
87.82
85.85
84.50
84.55
36
PGD
71,21
73.47
73.05
75.03
74.29
76.02
74.60
77.14|
76.46
74.81
75.00 76.41
6.3 SCALING-UP DEEP ORTHOGONAL NETWORKS WITH LIPSCHITZ BOUNDS
All previously proposed Lipschitz networks (Li et al., 2019b; Trockman & Kolter, 2021) consider only shallow architectures (S 10 layers). In this part, we investigate various factors to scale Lipschitz networks to deeper architectures: skip-connection, depth-width, receptive field, and down-sampling.
(1) Skip-connections. Conventional wisdom suggests that skip-connections mainly address the gradient vanishing/exploding problem; thus, they are not needed for orthogonal networks. To understand their role, we perform an experiment that trains deep Lipschitz networks without skip- connection and with skip-connections based on additionncoonatennatio (see Section 4). As shown in Table 4 (left), the network with additive skip-connection substantially outperforms the other two, and the one without ciip-coonettions performs the worst. Therefore, we empirically show that (additive) skip-connection is crucial in deep Lipschitz networks. (2) Depth and width. Exact orthogonality criticized for harming the expressive power of neural networks. We show that the decrease of expressive power can be alleviated by increasing the network depth/width. In Table 3 (Bottom) and Table 7 (Appendix E), we observe that deeper/wider architectures increase both the clean and robust accuracy. (3) Initialization methods. We try different initialization methods, including identical, permutation, uniform, and torus (Henaff et al., 2016; Helfrich et al., 2018). We find that identical initialization works the best for deep Lipschitz networks (> 10 layers). while all methods perform similarly in shallow networks as shown in Table 6 (Appendix E). (4) Receptive field and down-sampling. Previous works (Li et al., 2019b; Trockman & Kolter, 2021) use larger kernel
8

---

Under review as a conference paper at ICLR 2022
Table 4: (Left) Comparisons of various skip connection types on WideResNet22-D0 (kemel size 5). (Right) Comparisons of various receptive field and down-sampling types on WideResNet1O- 10. The symbols V. X indicate whether average pooling or strided convolution is used for sampliam For "slim" in strided convolution, we set kernel_ sinee_iieee stride; and for for "wide", kernel_sinn size stride kemel_sie _izee'izze (where kernel_ size' the kernel size for the main branch.
Receptive Field
Down-Sampling
Test Acc.
Kernel
Dilation
Pool
Stride
Clean
PGD
Test Acc.
Skip type
slim wide
80.70
68.81
Clean
PGD
82.36
70.36
ConvNet (w/o skip)
69.59
59.22
84.54
71.71
ShuffleNct (concat)
75.21
66.00
/
81.53
70.07
ResNet (add)
87.82
76.46
5
X
84.09
74.29
x
81,28
70.58
size and no stride for Lipschitz networks. In Table 4 (Right), we perform a study on the effeets of kernelddilation size and down-sampling types for the orthogonal convolutions. We find that an average pooling as down-sampling consistently outperforms strided convolutions. Furthermore, a larger kernel size helps to boost the performance. (5) Run-time and memory comparison. We find that previously proposed orthogonal convolutions such as CayleyConv, BCOP, and RKO require more GPU memory and computation time than SC-Fac. Therefore, we could not to scale them due to memory constraints (for 22 and 32 layers using Tesla V100 32G). In order to scale up Lipschitz networks. economical implementation of orthogonal convolution is crucial. As shown Figure 4, for deep and wide architectures, our SC-Fac is the most computationally and memory efficient method and the only method that scales to a width increase of 10 on WideResNNe222. Missing numbers in Figure 4 and Table 7 (Appendix E) are due to the large memory requirement.
Normal
SC-Fac
Cayley
BCOP
RKO
Inference Time (s)
Tran Tran Time 63
Menooyy (GB)
400
8
300
10
100
10
10
10
Width
Width
Width
Figure 4: Run-time and memory comparison using WideResNet22 on Tesla V100 32G. x-axis indicates width factor (channels = base channels x factor). Our SC-Fac is the most computationally and memory-efficient for wide architectures and is the only method that scales to width factor to 10 on WedeResNe122.. We also compare with ordinary network with regular convolutions and ReLU activations. Note that SC-Fac has the same inference speed as regular convolution the overhead from the GroupSort activations.
In summary, additive skip-connections are still essential for learning deep orthogonal networks. Due to the orthogonal constraints, is helpful to increase the depth/width of the network. However, this significantly increases the memory requirement; thus, a cheap implementation (like SC-Fac) is desirable. Finally, we find that larger kernel size and down-sampling based on average pooling is helpful, unlike standard practices in deep networks.
CONCLUSION
In this paper, we present paraunitary framework for orthogonal convolutions. Specifically, we estab- lish the equivalence between orthogonal convolutions in the spatial domain and paraunitary systems in the spectral domain. Therefore, any design for orthogonal convolutions is implicitly constructing paraunitary systems. We further show that the orthogonality for variants of convolution (strided, dilated, and group convolutions) also fully characterized by paraunitary systems. summary, paraunitary systems are all need to ensure orthogonality for diverse types of convolutions.
Based on the complete factorization ID paraunitary systems, we develop the first exact and complete design of separable orthogonal 2D 2D-convolutions. Our versatile design allows us to study the design principles for orthogonal convolutional networks. Consequently. we scale orthogonal networks deeper architectures, substantially outperforming their shallower counterparts. In experiments, we observe that exact orthogonality plays a crucial role in learning deep Lipschitz networks. In the future, plan to investigate other use cases that exact orthogonality is essential.

---

Under review as a conference paper at ICLR 2022
ETHICS STATEMENT
Our work lies in the foundational research on neural information processing. Specifically, we establish the equivalence between orthogonal convolutions in neural networks and paraunitary systems in signal processing. Furthermore, our presented orthogonal convolutional layers are plug-and-play modules that replace various convolutional layers in neural networks. Consequently, our modules applicable in Lipschitz networks for adversarial robustness, recurrent networks for learning long-term dependency, flow-based networks for effortless reversibility.
The vulnerability of neural networks raises concerns about their deployment in security-sensitive scenarios, such as healthcare systems or self-driving cars. In our experiment, we demonstrate successful application of orthogonal convolutions in learning robust networks. Furthermore, these networks achieve higher robust accuracy without additional techniques such as adversarial training or randomized smoothing. Therefore, our research contributes to the robust learning of neural networks and potentially leads to their broader deployment.
Furthermore, we reduce the inference cost of our layer to be the same as a traditional convolution layer, significantly lowering the expense for deployment compared with other methods for orthogonal networks. However, our layers are memory and computationally more expensive during training than traditional layers. The overhead to the already expensive training cost exacerbates the concerns on the efficacy of learning neural networks. Therefore, balancing between robustness and efficiency an important research topic that requires more research the future. We develop more efficient implementation than previous approaches, narrowing the gap between these two conflicting goals.
REPRODUCIBILITY STATEMENT
We provide detailed proofs to our theoretical claims in Appendices B to D. We describe experimental setups and training details of our models in Appendix E. We include our code for experiments in the supplementary material.
REFERENCES
Cem Anil, James Lucas, and Roger Grosse. Sorting out lipschitz function approximation. In International Conference Machine Learning, pp. 291-301, 2019.
Aharon Azulay and Yair Weiss. Why do deep convolutional networks generalize poorly to small image transformations? Journal of Machine Learning Research, 20(184):1 2019.
Nitin Bansal, Xiaohan Chen. and Zhangyang Wang. Can we gain more from orthogonality regular- izations in training deep cnns? In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pp. 4266-426624 4276. Curran Associates Inc., 2018
Jens Behrmann, Will Grathwohl, Ricky TQ Chen, David Duvenaud, and Jörn-Henrik Jacobsen. Invertible residual networks. In International Conference on Machine Learning, pp. 573-582. PMLR, 2019.
Åke Björck and Clazett Bowie. An iterative algorithm for computing the best estimate of an orthogonal matrix. SIAM Journal on Numerical Analysis, 8(2):358-364, 1971.
Minmin Chen, Jeffrey Pennington, and Samuel Schoenholz. Dynamical isometry and a mean field theory of mns: Gating enables signal propagation in recurrent neural networks. In International Conference on Machine Learning, pp. 873-882, PMLR, 2018.
Ricky TQ Chen, Jens Behrmann, David K Duvenaud, and Joern Been-keerik Jacobsen. Residual flows for invertible generative modeling. Advances in Neural Information Processing Systems, 32, 2019.
Artem Chernodub and Dimitri Nowicki. Norm-preserving orthogonal permutation linear unit activa- tion functions (oplu). arXiv preprint arXiv: 02313, 2016.
Moustapha Cisse, Piotr Bojanowski, Edouard Grave, Yann Dauphin, and Nicolas Usunier. Parseval networks: Improving robustness to adversarial examples. International Conference on Machine Learning, pp. 863. PMLR, 2017.
10

---

Under review as a conference paper at ICLR 2022
Laurent Dinh, David Krueger, and Yoshua Bengio. Nice: Non-linear independent components estimation. arXiv preprint arXiv:1410.851,, 2014.
Laurent Dinh, Jascha Sohl-Dickstein, and Samy Bengio. Density estimation using real nvp. arXiv preprint arXiv: 088000, 2016.
Victor Dorobantu, Per Andre Stromhaug, and Jess Renteria. Dizzyran: Reparameterizing recurrent neural networks for norm-presse corm-preserving backpropagation. arXiv preprint arXiv: 2016.
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In Proceedings of the thirteenth international conference on artificial intelligence and statistics, pp. 249-256. JMLR Workshop and Conference Proceedings. 2010.
Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. arXiv preprint arXiv:1412.6572. 2014.
Will Grathwohl, Ricky TQ Chen, Jesse Bettencourt, Ilya Sutskever, and David Duvenaud. Ffjord: Free-form continuous dynamics for scalable reversible generative models. arXiv preprint arXiv:1810.01367. 2018.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016a.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Identity mappings in deep residual networks. In European Conference on Computer Vision, pp. 630-645 Springer, 2016b.
Kyle Helfrich, Devin Willmott, and Qiang Ye. Orthogonal recurrent neural networks with scaled cayley transform. In International Conference on Machine Learning, pp. 1969-1978. PMLR, 2018.
Mikael Henaff, Arthur Szlam, and Yann LeCun. Recurrent orthogonal networks and long-memory tasks. In International Conference on Machine Learning, pp. 2034-22440 2042, 2016.
Nicholas Higham. The scaling and squaring method for the matrix exponential revisited. SIAM review, (14)77477774, 2009.
Jie Hu, Li Shen, and Gang Sun. Squeeze-and-exciiation networks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 7132-7141, 2018.
Gao Huang. Zhuang Liu, Laurens Van Der Maaten, and Kilian Q Weinberger. Densely connected convolutional networks. In CVPR, volume pp. 3, 2017.
Lei Huang, Li Liu, Fan Zhu, Diwen Wan, Zehuan Yuan, Bo Li, and Ling Shao. Controllable orthogonalization in training dnns. In Proceedings of the IEEE/VVF Conference Computer Vision and Pattern Recognition, pp. 6429 2438, 2020.
Barry Hurley and Ted Hurley. Paraunitary matrices. arXiv preprint arXiv:1205.0703 2012.
Sergey Ioffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International conference on machine learning, pp. 448-456 PMLR, 2015.
Kui Jia, Dacheng Tao, Shenghua Gao, and Xiangmin Xu. Improving training of deep neural networks via singular value bounding. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 4344 4352, 2017.
Kui Jia, Shuai Li, Yuxin Wen, Tongliang Liu, and Dacheng Tao. Orthogonal deep neural networks. IEEE transactions on pattern analysis and machine intelligence, 2019.
Li Jing, Yichen Shen, Tena Dubcek, John Peurifoy, Scott Skirlo, Yann LeCun, Max Tegmark, and Marin Soljačić. Tunable efficient unitary neural networks (cunn) and their application to mns. In International Conference Machine Learning, pp. 1733-1741. PMLR, 2017.

---

Under review as a conference paper at ICLR 2022
Jaroslav Kautsky and Radka Turcajová. A matrix approach to discrete wavelets. In Waveler Analysis and Its Applications, volume 5, pp. 117-135. Elsevier, 1994.
Durk P Kingma and Prafulla Dhariwal. Glow: Generative flow with invertible 1x1 convolutions, In Advances in neural information processing systems, pp.
2018.
Ivan Kobyzev, Simon Prince, and Marcus Brubaker. Normalizing flows: An introduction and review of current methods. IEEE Transactions on Puttern Analysis and Machine Intelligence, 2020.
Mario Lezcano Casado. Trivializations for gradient-based optimization on manifolds. Advances in Neural Information Processing Systems, 32:9157-9168, 2019.
Mario Lezcano-Casade and Davidd Martínez-Rubio. Cheap orthogonal constraints in neural networks: A simple parametrization of the orthogonal and unitary group. In International Conference on Machine Learning, pp. 3794-3803, 2019.
Jun Li. Fuxin Li, and Sinisa Todorovic. Efficient riemannian optimization on the stiefel manifold via the cayley transform. In International Conference on Learning Representations, 2019a.
Qiyang Li. Saminul Haque, Cem Anil, James Lucas, Roger B Grosse, and Ben-Henrik Jacobsen. Preventing gradient attenuation lipschitz constrained convolutional networks. Advances in neural information processing systems, pp. 15390-15402, 2019b.
Yuan-Pei Lin and PP Vaidyanathan. Theory and design of two-dimensional filter banks: review. Multidimensional Systems and Signal Processing, 7(3-4):263-330, 1996.
Sheng Liu, Xiao Li, Yuexiang Zhai, Chong You, Zhihui Zhu, Carlos Fernandez-Grandaa and Qing Qu. Convolutional normalization: Improving deep convolutional network robustness and training. Advances in Neural Information Processing Systems, 34, 2021.
Ningning Ma, Xiangyu Zhang, Hai-Tao Zheng, and Jian Sun. Shufflenet v2: Practical guidelines for efficient enn architecture design. In Proceedings of the European conference on computer vision (ECCV), pp. 116-131, 2018.
Kehelwala DG Maduranga, Kyle E Helfrich, and Qiang Ye. Complex unitary recurrent neural networks using scaled cayley transform. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 4528-4535, 2019.
Alexander Mathiasen, Frederik Hvilshøj, Jakob Rødsgaard Jørgensen, Anshul Nasery, and Davide Mottin. What if neural networks had svds? arXiv preprint UrXiv:2009.3397) 2020.
Zakaria Mhammedi, Andrew Hellicar, Ashfaqur Rahman, and James Bailey. Efficient orthogonal parametrisation of recurrent neural networks using householder reflections. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pp. 2401-2409 2017.
Takeru Miyato, Toshiki Kataoka, Masanori Koyama, and Yuichi Yoshida. Spectral normalization for generative adversarial networks. International Conference on Learning Representations, 2018.
Behnam Neyshabur, Srinadh Bhojanapalli, and Nathan Srebro. A pac-bayesian approach to spectrally- normalized margin bounds for neural networks. In International Conference on Learning Repre- sentations, 2018.
Alan V. Oppenheim, Alan S. Willsky, and S. Hamid Nawab. Signals & Systems (2nd Ed.). Prentice- Hall, Inc., 1996.
George Papamakarios, Eric Nalisnick, Danilo Jimenez Rezende, Shakir Mohamed, and Balaji Lakshminarayanan. Normalizing flows for probabilistic modeling and inference. arXiv preprint arXiv:19/2.00266, 2019.
Jeffrey Pennington, Samuel S Schoenholz, and Surya Ganguli. Resurrecting the sigmoid in deep learning through dynamical isometry: theory and practice. Proceedings of the 31st International Conference Neural Information Processing Systems, pp. 4788 4798,4798, 2017.
12

---

Under review as a conference paper at ICLR 2022
Jeffrey Pennington, Samuel Schoenholz, and Surya Ganguli. The emergence of spectral universality in deep networks. In International Conference on Artificial Intelligence and Statistics, pp. 1924-1932 PMLR. 2018.
Haozhi Qi, Chong You, Xiaolong Wang, Ma, and Jitendra Malik. Deep isometric learning for visual recognition. In International Conference on Machine Leurning, pp. 7824-7835. PMLR, 2020.
Hanie Sedghi, Vineet Gupta, and Philip M Long. The singular values of convolutional layers. In International Conference on Learning Representations, 2019.
Sahil Singla and Soheil Feizi. Skew orthogonal convolutions. arXiv preprint arXIv:2105.11417, 2021.
Gilbert Strang and Truong Nguyen. Wavelets and filter banks. SIAM, 1996.
Mingxing Tan and Quoe Le. Efficientnet: Rethinking model scaling for convolutional neural networks.
In International Conference on Machine Learning, pp. 6105-6114, PMLR, 2019.
Asher Trockman and Zico Kolter. Orthogonalizing convolutional layers with the cayley transform. In International Conference on Learning Representations, 2021.
PP Vaidyanathan. Multirate systems and filter banks. Prentice-Hall Inc., 1993.
Rianne Van Den Berg, Leonard Hasenclever, Jakub M Tomczak, and Max Welling. Sylvester normalizing flows for variational inference. In 34th Conference on Uncertainty in Artificial Intelligence 2018, UAI 2018, pp. 393-402. Association For Uncertainty in Artificial Intelligence (AUAI), 2018.
Shankar Venkataraman and Bernard C Levy. comparison design methods for 2-d fir orthogonal perfect reconstruction filter banks. IEEE Transactions Circuits and Systems II: Analog and Digital Signal Processing, 42(8):525-536, 1995.
Eugene Vorontsov, Chiheb Trabelsi, Samuel Kadoury, and Chris Pal. On orthogonality and learning recurrent networks with long term dependencies. In International Conference on Machine Learning. pp. 3570-3578, 2017.
Jayun Wang. Yubei Chen, Rudrasis Chakraborty, and Stella X Yu. Orthogonal convolutional neural networks. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2019.
Eric Wong, Frank R Schmidt, Jan Hendrik Metzen, and Zico Kolter. Scaling provable adversarial defenses. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pp. 2410-8419, 2018.
Eric Wong, Leslie Rice, and Zico Kolter. Fast better than free: Revisiting adversarial training. In International Conference Learning Representations, 2020.
Lechao Xiao, Yasaman Bahri, Jascha Sohl-Dickstein, Samuel Schoenholz, and Jeffrey Pennington. Dynamical isometry and mean field theory of cnns: How to train 10,000-layer vanilla convolu- tional neural networks. In International Conference on Muchine Learning, pp. 5393-5402. PMIR, 2018.
Di Xie, Jiang Xiong, and Shiliang Pu. All you need is beyond good init: Exploring better solution for training extremely deep convolutional neural networks with orthonormality and modulation. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 61 6176-6185, 2017.
Chengxi Ye, Matthew Evanusa, Hua He, Anton Mitrokhin, Tom Goldstein, James A Yorke, Cornelia Fermuller, and Yiannis Aloimonos. Network deconvolution. In International Conference on Learning Representations, 2020.
Jiong Zhang, Qi Lei, and Inderjit Dhillon. Stabilizing gradients for deep neural networks via efficient svd parameterization. In International Conference on Machine Learning, pp. 5806-5814, 2018 8a.
13

---

Under review as a conference paper at ICLR 2022
Xiangyu Zhang, Xinyu Zhou, Mengxiao Lin, and Jian Sun. Shufflenet: An extremely efficient convolutional neural network for mobile devices. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 6848-6856 2018b.
Jianping Zhou Multidimensionall Multirate Systems: Characterization, Design, and Applications. Citeseer, 2005.
14

---

Under review as a conference paper at ICLR 2022
Appendices: Scaling-up Diverse Orthogonal Networks by Paraunitary Framework
Arthogonal Convolutional
Notations. We use non-bold letters for scalar (e.g., 2) and bold ones for vectors or matrices (e.g., x)) We denote sequences in the spatial domain using lower-case letters (e.g.. x [n]. æff]) and their spectral representations using caper-case letters (c.g., (2), (=)). For a positive integer, say R E Z+, we abbreviate the set {0, 1.... R 1 as [R], and whenever possible, we use its lower-case letter, say r E [R]. as the corresponding iterator.
Assumptions. For simplicity, we assume all sequences are L with range 2 (0, #2, (a sequence = [=[n]. n ]} is if Enez ||][n]]]] < oo). Such assumption is common in the literature, which avoids boundary conditions in signal analysis. To deal with periodic sequences (finite sequences with circular padding), one can either adopt the Dirac function in the spectral domain or use discrete Fourier transform to compute the spectral representations. In our implementation, we address the boundary condition case by case for each convolution type, with which we achieve exact orthogonality in the experiments (Section 6.1).
A PSEUDO CODE FOR OUR SC-FAC ALGORITHM
We include the pscudo-code for separable complete factorization (Section 2) in Algorithm I and diverse orthogonal convolutions (Section 3) Algorithm The pseudo-code in Algorithm I consists of three parts: (1) First, we obtain orthogonal matrices from skew-symmetric matrices using matrix exponential. We use GeoTorch library (Lezcano Casado, 2019) for the function matrix_exx in our implementation: (2) Subsequently, we construct two ID paraunitary systems using these orthogonal matrices; (3) Lastly, we compose two ID paraunitary systems to obtaín one 2D paraunitary systems The pseudo-code in Algorithm 2 consists of two parts: (1) First, reshape each paraunitary system into an orthogonal convolution depending on the stride; and (5) second, we concatenate the orthogonal kernels for different groups and return the output.
B ORTHOGONAL CONVOLUTIONS VIA PARAUNITARY SYSTEMS
In this section, we prove the convolution theorem and Parseval's 's theorem for standard convolutional layers. Subsequently, we prove the paraunitary theorem which establishes the equivalence between orthogonal convolutional layers and paraunitary systems.
B. SPECTRAL ANALYSIS OF STANDARD CONVOLUTION LAYERS
Standard convolutional layers are the default building blocks for convolutional neural networks. One such layer consists of a filter bank with T x S filters h [ E E)eerr,eeE(s) where S, T are the number of input and output channels respectively. The layer maps an S-channel input
[i, =) to a T-channel output y {v [he according to
Ve [i]
Σ .E(S] nEZ
[m) [0n]2.12 nl.
(B.1)
where indexes the output location to be computed, and n indexes the filter coefficients. Alternatively, we can rewrite Equation (B.1) in matrix-vector form as
v
Σ hmnaali m)). neZ
(B.2)
where each hnn] TxXS is matrix, and each ærii n] TR. or y(1] E RT is vector.
Notice that in Equation (B.2), we group entries from all channels into a vector or matrix (e.g.. from (zo [n]].sss] [s] to ar(1)), different from a common notation that groups entries from all locations into vector matrix (e.g., from [I,[n],n n E Z} into xg). In the matrix- vector form, standard convolutional layer computes a vector sequence y = { E IT' i E Z} with a convolution between matrix sequence h- (h(r) [n) T E Z) and vector sequence [ar R E Z).
15

---

Under review as a conference paper at ICLR 2022
Algorithm 1: Separable Complete Factorization (SC-Fac)
Input: Number of channels C, kernel size 2L + I. and
Skew-symmetric matrices {
(6) with A E RRCxC vl E [-L, 4J, d e {1,2}.
Output: A paraunitary system H E C
Initialization: Sample N/d from {1, C) uniformly 44 E - L,, (1,2) / Iterate for vertical/horizonte
cimensions
+/
for d = 1 to 2 do
/+ 1) Compute orthogonal matrices from skew-symmetric matrices
/+ Iterate for filter locations
for f = L to L do
if f then
Qa + matrix_exp(AA // use matrix_exp() in GeoTorch (Lezcano Casado, 2019)
else
U + select ( ( cols N/0) selects the first cols
columns of the matrix
end if end for
/+ 2) Compose 1D paraunitary systems from orthogonal matrices
Hed f- Q₂
for L to L do
Hyd - convlddddlnoooo (HdddddHd U L-U
I - U U(
u'! ] Had
Hy - convid
end for end for
/+ 3) Compose 2D paraunitary systems from 1D paraunitary
H + Compose H22 // i.e., Hasa. = (Ha)a where the 1D
paraunitary systems Hi and H2 are of size C
return H.
Algorithm 2: Construct Diverse Orthogonal Convolutions from Paraunitary Systems
Input: Number of base channels C, kernel size K R(2L + 1),
stride R, dilation D, number of groups G Output: An orthogonal kernel W E IR x
Set K" <- K/R, number of imput channels < GC/R² and output channels + GC
for y = 0 to G do
/+ 1) Construct orthogonal convolutions from paraunitary systems
Initialize skew-symmetric matrices {(4(6 (t,)) 1/-112 for the current
H + Algorithm 1: SC-Fac(C, K', (L, _ -
(4.g)
H + reshape(HH" (C,C,K',K)) + (C/R2, (C, K,K
end for
2) Concatenate orthogonal convolutions from different groups
W < concatenate (?L)) G-= dim = 0)
return W (where the filter for input channel s and output channel is W Westn E RKxx)
Let us first define the Z-transform and various types of Fourier transform in Definition B.1 before proving the convolution theorem (Theorem 2.1).
16

---

Under review as a conference paper at ICLR 2022
Definition B.1 (Z-transform and Fourier transforms). For sequence (of scalars, vectors, matrices) a = {a [n], n E 2}, its Z-transform X (() defined as
X(=)
Σ nEZ
x a[n]=
(B.3)
where z E C is a complex number such that the infinite sum is convergent. If 2 is restricted to the unit circle 2 = سi" (i.e., |z| =), the 2-transform ((2 reduces to discrete-time Fourier transform (DTFT) X )ee"). If is further restricted to finite set w E {2rk/N,k k E [N]], the DIFT X ((e)) reduces to an N- N-points discrete Fourier transform (DFT) X (cllak/N).
The celebrated convolution theorem states that the convolution in spatial domain (Equation (B.2)) is equivalent to multiplication in the spectral domain, i.e., (() (z), V2 C.
Proof of Theorem 2.1. The proof follows directly from the definitions of standard convolution (Equa- tion (B.2)) and Z-transform (Equation (B.3)).
( Σ y
(B.4)
i2
Σ AEEZ
h[n]z//i - ml x-1
(B.5)
iE
Σ
h[m]2-1
Σ x 21/2-(1-1) (1-1))
(B.6)
nEZ
VEE
h/nl2
Σ KEZ
x [b]]
(B.7)
(2))
(B.8)
where Equations (B.4) and (B.8) use the definition of Z-transform, Equation (B.5) uses definition of convolution, and Equation (B.7) makes change of variable k: =
Next, we introduce the concepts of inner product and Frobenius norm for sequences. We then prove Parseval's theorem, which allows us to compute the sequence norm in the spectral domain.
Definition B.2 (Inner product and norm for sequences). Given two sequences x = {ar(m), n E Z) and y [v(m), E Z) with a [[]], [ni) having the same dimension for all n, the inner product of these two sequences is defined
y) A E(alr) (a(n).y(m))
(B.9)
where (x) y[m]) denotes the Frobenius inner product between axn] and y[n]. Subsequently, we can define the Frobenius norm of sequence using inner product as
V(z x)
(B.10)
Theorem B.3 (Parsavel's theorem), Given a sequence x = {m(n), E Z.,, its sequence norm ||] can be computed by (elw) in the spectral domain
|
Σ
|
1
1" ||x ([x(c)
(B.11)
2
nEZ
where [((eh)1122 X (elw)t x (())) is an inner product between complex arrays.
17

---

Under review as a conference paper at ICLR 2022
Proof of Theorem B.3. The theorem follows from the definitions of convolution and discrete- time Fourier transform (DTFT).
1
1
x
((e) du
(X(elly (ellw) X ((elw) dw
(B.12)
2T
2T
1
Σ x ar[mle jumm ) dw
x x/mile J jun
(B.13)
2m
mEZ
Σ
Σ
(x=[n] amml)
e e-jw(m dw
(B.14)
2x
REZ mEZ
Σ
(00[x] [c[m]>>> m=
(B.15)
NEZ mEZ
Σ NEZ
(2 in], x<1l)> = Σ |
(B.16)
NEZ
where Equation (B.14) is due to the bi-linearity of inner products, and Equation (B.15) makes uses of junk dw 1 du 2π for k 0.
the fact that 1 e juck dw for and 1_
B.2 EQUIVALENCE BETWEEN ORTHOGONAL CONVOLUTIONS AND PARAUNITARY SYSTEMS
With the sequence norm introduced earlier, we formally define orthogonality for convolutional layers. Definition B.4 (Orthogonal convolutional layer). A convolution layer orthogonal if the input norm ||||| is equal to the output norm ||y|] for arbitrary input I, that is
|g
|
| A ||z||,
(B.17)
nEZ
where ||a]|| (or ||y|| is defined the squared root of Enez ||][n]]] for Enez ||,||]]]2)
This definition of orthogonality not only applics to standard convolutions in Equation (B.2) but also variants of convolutions in Appendix C.3. In this section, however, we first establish the equivalence between orthogonality for standard convolutions and paraunitary systems.
Theorem B.5 (Paraunitary theorem). A standard convolutional layer (in Equation (B.2)) is orthogo- nal (by Definition B.4) if and only if its transfer matrix (z) is paraunitary, i.e.,
H (=)) (()) = I, M=|=111 H (ee
H (( = I, Ve R.
(B.18)
In other words, the transfer matrix H (ct²) unitary for all frequencies ws e R.
Proof of Theorem B.5. We first prove that convolutional layer is orthogonal if its transfer matrix H (2) is paraunitary (i.e., (elw) is unitary for any frequency w E IR).
1
Y (et
du
(B.19)
2x
H (( (( ((tu))) du
(B.20)
2x
x (e) de
(B.21)
2x
||=||"
(B.22)
where Equations (B.19) and (B.22) due to Parseval's theorem (Theorem B.3), Equations (B.19) and (B.20) follows from the convolution theorem (Theorem 2.1), and Equation (B.21 utilizes that
H (e!") is unitary for any frequency E R (thus (el")) X (e(")) || (e!")] || for any X ((e/"))
The 'only if' part also holds in practice. We here prove by contradiction using periodic inputs (e.g.. finite inputs with circular padding). Suppose there exists frequency and H (elw) is not unitary.
18

---

Under review as a conference paper at ICLR 2022
Since H (cl")) is continuous (due to h L and dominated convergence theorem), there exist integers N, k, such that = 2k /N and H (elRk/NN is also not unitary. As result, there exists complex vector such that H (elAnk/N) yu while ||l|| o |ull Therefore, we can construct two periodic sequences a = {a [n], [N]} and y = [y[n]. n E [N]) such that
m|n] ue Bank/NN
(B.23)
Now the input norm ||س||| /
VENEIN |
N | not equal to the output norm ||y/|
EnE(N] | = / w/I, i.e. the layer not orthogonal, which leads to a contradiction.
C A PARAUNITARY FRAMEWORK FOR ORTHOGONAL CONVOLUTIONS
Section B.2
Section B.3
Section B,4
Spectral Trausformation
Spectral Factorization
Orthogonal
Paraunitary Systems
Orthogonal Matrices
Parameterization
Unconstrained Parameters
Conv. Layers
Standard Conv,
Separable BCOP
Mat. Exp.
Dilated Conv.
Cayley
Strided Conv.
Björek
Group Conv.
Parameterization
CayleyConv
SOC
Figure A framework for designing orthogonal convolutional layers. In Appendix C.2, we unify variants of orthogonal convolutions in the spectral domain and show that their designs reduce to con- structing paraunitary systems. In Appendix C.3, we show that paraunitary system can be constructed with different approaches: our approach and BCOP (Li et al., 2019b) represent the paraunitary using orthogonal matrices, while CayleyConv (Trockman & Kolter, 2021) and SOC (Singla & Feizi, 2021) directly parameterizes it using unconstrained parameters. In Appendix C.4, we investigate various parameterizations for orthogonal matrices, such as matrix exponential, Cayley transform, and Björck orthogonalization.
C.1
ANALYSIS
Multi-resolltion operations are essential in various convolutional layers, in particular strided and dilated convolutions. In order to define and analyze these convolutions rigorously, we first review the concepts of up-sampling, down-sampling, and polyphase components.
(1) Up-sampling. Given sequence (of scalars, vectors, matrices) x [a[m] E Z}, its up- sampled sequence tt {x 1 [[]], E 2} is defined as
[x[n/R] 0 (mod R)
x
(C.1)
otherwise
where R - is the up-sampling rate. Accordingly, we denote the Z- transforrm of x1 as
x (²) Σ x [n]2=
(C.2)
nEZ
The following proposition shows that X (x) is easily computed from X (()).
Proposition C.1 (Z-transform of up-sampled sequence). Given sequence and its up-sampled sequence x 1R. their Z-transforms X (z) and x (z) are related by
X ((2
(C.3)
19

---

Under review as a conference paper at ICLR 2022
Proof of Proposition C.I. The proof makes use of the definition of Z- Z-transformm (Equation (B.3)).
xt (z)
=
Σ x R
[n]
(C.4)
REZ
Σ x'
R [mil]=- m
(C.5)
mE2
Σ mEZ
x
[m] (= = X())),
(C.6)
where Equation (C.5) makes change of variables n/ R. since ( [n] 0, Vn & mR.
(2) Down-sampling and polyphase components. Different from the up-sampled sequence, there exist multiple down-sampled sequences. depending on the phase of down-sampling, These sequences are known as the polyphase components. Specifically, given sequence scalars, vectors, or matrices) [æ[n], n E}, its yth polyphase component w [x+1"[n], E 2} defined as
[' - =fnR++ +r),
(C.7)
where + the down-sampling rate. We further denote the Z-transform of w as
(2)
Σ x [r][
(C.8)
nEZ
Note that r Z is arbitrary integer, which does not necessarily take values from [R]. In fact, have x (r(++)))
x [In k] and X X*+kR( 2t xx)) In Proposition C.2, establish [E[R). i.e., to represent (2) in terms of (H) (r(R)) Proposition C.2 (Polyphase decomposition). Given a sequence and its polyphase components wrlR's the Z-transform X (z) can be reprexented by (x*)"())retp)) as
the relation between (2) and [ (=))r<())))
X(2)
Σ (=))(=
(C.9)
rE(R]
Proof of Proposition C.2. We start with X X(2), and try to decompose it into its polyphase components {2),()),.... X R- (2).
X (=)
Σ æ[n|z
(C.10)
nEZ
Σ
Fe|mR- + r]= (m=
(C.11)
rE] [R] mEZ
Σ
Σ
x [m R + -m 2-
(C.12)
ME [R]
AMEZ
Σ
z- x R [m]
(C.13)
rE(
AMEZ
= Σ
x (x
(C.14)
rE(R)
where Equation (C.11) makes a change of variables mR++r and Equation (C.13) is the definition of polyphase components [m] (mmm
æmmR + r
For simplicity, we stack R consecutive polyphase components into polyphase matrices as
x (=)
[
X R (2)
x (2); (
(C.15)
x R
The following proposition extends the Parseval's theorem in Theorem B.3 and shows that the sequence norm ||a:|| can also be computed in terms of the polyphase matrix X [R] (z) (or X (z)).
20

---

Under review as a conference paper at ICLR 2022
Proposition C.3 (Parseval's theorem for polyphase matrices). Given sequence its sequence (1)) (etw)) in the spectral domain as
norm ||0|| can be computed by X [R] (elw) (or X
Ri (dwu) x
|| du
x R (dw)) dw.
(C.16)
2π
2x
Proof of Proposition C.3. The proof follows the standard Parseval's theorem in Theorem B.3. We only prove the first part of the proposition (using X
(R as follows.
x
2
||=]|]]]]
(C.17)
REZ
| - r]]
(C.18)
re [ mEZ
a 112 [ma) 2
Σ Σ
(C.19)
rE(R] R MEZ
Σ
du
(C.20)
2T
rE[R]
18) (ebir)
|| dw,
(C.21)
2T
where Equation (C.17) follows the definition of sequence norm, Equation (C.18) changes variables as n mR + r, Equation (C.19) is the definition of polyphase components, and Equation (C.20)
applies Parseval's 's theorem to xx" Rs.. The second part (using X X|R| (ell)) can be proved similarly. O
C.2 UNIFYING VARIOUS CONVOLUTIONAL LAYERS IN THE SPECTRAL DOMAIN
In Appendix B, the convolution theorem states that standard convolutional layer is matrix vector product Y (2) = H X (2) in the spectral domain, and the layer is orthogonal if and only H2) paraunitary (Theorem B.5). However, the canonical convolution theorem does hold for variants of convolutions, thus enforcing a paraunitary (2) may not lead to orthogonal convolution. this subsection, we address this limitation by showing that various convolutions can be uniformly written as (z)) = X()), where Yz).. (2),, (z)) are some spectral representations of h, æ. Subsequently, we prove that any of these layers is orthogonal if and only if its H(2) is paraunitary.
(1) Strided convolutional layers are widely used in neural networks to adjust the feature resolution: strided convolution layer decreases the resolution by down-sampling after standard convolution, while transposed convolution increases the resolution by up- up-sampling before standard convolution.
Formally, strided convolutional layer with stride R (abbrev. R-sttiided convolution) computes its output following
y Σ
hin]a[/Ri n].
(C.22)
In contrast, a transposed strided convolutional layer with stride R (abbrev. as R-strided convolution) computes its output according to
y
Σ nEZ
h/j]xtRR tR [z]]..
(C.23)
Proposition C.4 (Orthogonality of strided convolutional layers). For a R-strided convolution, the spatial convolution in Equation (C.22) leads to the following spectral representation:
(=) = H (2) (2)
(C.24)
And for an 1 R-strided convolution, the spatial convolution is represented in spectral domain as: ( H (=)((()
(C.25)
Furthermore, a 1. R-strided convolution is orthogonal and only if H [
(x) is paraunitary, and an t R-strided convolution is orthogonal if and only if H [R] is paraunitary.
21

---

Under review as a conference paper at ICLR 2022
Proof of Proposition C.4. (1a) J R-strided convolutions. We first prove the spectral representation of I R-stridedd convolution in Equation (C.24).
Y(=) Σ y Σ
Σ neE
h h(n]a: Rá ml =
(C.26)
IEZ
iE?
Σ
Σ
h(mR r|a0(( ( x-
(C.27)
rE]A] mEZ
Σ> æ0(i m) + r/z (1-m)) ))
Σ
Σ AMEZ
h/mR -|==-
Σ
(C.28)
rE[R]
E
Σ
h/mR r|a-
Σ WEE
201' +r
(C.29)
ME
Σ
H (2)x* (2),
(C.30)
rE[R]
where Equation (C.26) follows from the definitions of the J. R-strided convolution (Equation (C.22))
and the Z-transform (Equation (B.3)), Equation (C.27) makes a change of variables n = mß r, Equation (C.29) further changes i' = and Equation (C.30) is due to the definition of polyphase components (Equation (C.7)). Now We rewrite the last equation concisely as
X (2)
Y(x) H (IR(())
H (R (2)]
(C.31)
X (2)
H (2)
X (2)
which is the spectral representation of 4 R-strided convolutions in Equation (C.24).
Now we prove the orthogonality condition for J R-strided convolutions.
| 2
Y Y(dh dw
(C.32)
2T
H [R] (clwe) ) ( dw
(C.33)
2m
x (1]) (c (222)) ||2eeu dw
(C.34)
2x
| 12_
(C.35)
where Equations (C.32) and (C.35) are due to Parseval's theorems (Theorem B.3 and Proposition C.3), Equation (C.33) follows from the spectral representation of the & R-strided convolution (Equa- tion (C.24)), and Equation (C.34) utilizes that the transfer matrix is unitary at each frequency. The "only if" part can be proved by contradiction similar to Theorem B.5.
(1b) R-strided convolutions. According Proposition C.1, the Z-transform of x is X(=)). Therefore, an application of the convolution theorem (Theorem 2.1) on Equation (C.23) leads us to
(x) = H (x) (x))
(C.36)
Expanding Y (2)) and (z) using polyphase decomposition (Proposition C.2), we have
Σ Y R (2 R --=
Σ rE[R]
(2T
X(2
(C.37)
rE[R]
Σ Yr (2 )T= Σ R xx(x))) x-
(C.38)
rE[R]
rE(R]
(2 1n
Vr E [R]
(C.39)
(2) 1R X (2), Vr [R],
(C.40)
22

---

Under review as a conference paper at ICLR 2022
where Equation (C.39) is due the uniqueness of Z-transform, and Equation (C.40) changes the variables from to 2. We can rewrite the last equation in concisely as
(2)
(2)
(2)
H H
X(=),
(C.41)
(2)))R(2))
H (2))
(2)
H (2)
which is the spectral representation of f R-strided convolutions in Equation (C.25).
Lastly, we prove the orthogonality condition for 1 R-strided convolutions.
1
Y y (c o|² dw
|
(C.42)
2x
1
H (edw) )x (ctr)]
(C.43)
2x
1
/"
Xx (( di
(C.44)
2m
||2
(C.45)
where Equations (C.42) and (C.45) are due to Parseval's theorems (Theorem B.3 and Proposition C.3), Equation (C,43) follows from the spectral representation of the R-strided convolution (Equa- tion (C.25)), and Equation (C.44) uses the fact that the transfer matrix unitary for each frequency. The "only if" part can be proved by contradiction similar to Theorem B.5.
(2) Dilated convolutional layer is proposed to increase the receptive field of a convolutional layer without extra parameters and computation. The layer up-samples its filter bank before convolution with the input. R-dilated convolutional layer) computes its output with the following equation:
Σ h [n]ali n)
(C.46)
nEZ
Proposition C.5 (Orthogonality of dilated convolutional layer). For an R-dilated convolution, the spatial convolution in Equation (C.46) leads to spectral representation as
(z) = H (x
(C.47)
Furthermore, an R-dilated convolutional layer orthogonal and only if (( is paraunitary.
Proof of Proposition C.5. According to Proposition C. the Z-transform of ht is H2) There- fore, the "if" part follows directly from the convolution theorem. The "only if" part can proved by constructing counterexample similar to Theorem B.5,
Notice that H(2 is paraunitary if and only if (elw) is unitary for all frequency w E R, which is the same as Hz being paraunitary. In other words, any filter bank that orthogonal for a standard convolution is also orthogonal for dilated convolution and vice versa.
(3) Group convolutional layer is proposed reduce the parameters and computations and used in many efficient architectures, including MobileNet, ShuffleNet. The layer divides both input/output channels into multiple groups and restricts the connections within each group.
Formally, group convolutional layer with G groups (abbrev. as G-group convolutions) is parame- terized by filter banks (h² [h]]) each consists of (T/G) (S/G) filters. The layer maps an S channels input æ to a I' channels output according to
y f
Σ bikdiag ([h( ( x n).
(C.48)
where blkdiag((1) (+)) computes block diagonal matrix from set of matrices.
23

---

Under review as a conference paper at ICLR 2022
Proposition C.6 (Orthogonality of group convolutional layer). For G-group convolation, the spatial convolution in Equation (C.48) leads a spectral representation as their z-transforms satisfy
(2) blkdiag ((H (=)) X
(C.49)
Furthermore, a G-group convolutional layer is orthogonal if and only if the block diagonal matrix paraunitary, i.e., each h (z) is paraunitary.
Proof of Proposition C.6. Due to the convolution theorem, suffices to prove that the Z-transform of sequence of block diagonal matrices is also block diagonal in the spectral domain.
h [n]
Enez h. [m]2-=
(C.50)
WEZ
h G G [n]
Σnezhe (n=
blkdiag ((h" (n) (
(x)
(C.51)
blkdiag ((H (2))
{=)
As result, write the orthogonality condition as
(2)
(2)
G- G-1(x))
Hx-1(x)
H2
= I, V|2|=1. 11
(C.52)
HC-1 Hc-
The equation implies (z) Hz(2) 1, M= 1, 1 [G], i.e. each Hz(z) is paraunitary.
C.3 REALIZATIONS OF PARAUNITARY SYSTEMS
In this subsection, we first prove that all finite-length ID-paraunitary systems can be represented in factorized form. Next, we show how we can construct MD MD-paraunitary systems using 1D systems. Lastly, we study the relationship of existing approaches to paraunitary systems.
C.3.1 COMPLETE FACTORIZATION OF ID-PARAUNITARY SYSTEMS
The classic theorem for spectral factorization of paraunitary systems is traditionally developed for causal systems (Vaidyanathan, 1993; Kautsky & Turcajová, 1994). Given a causal paraunitary system of length L, (i.e., polynomial in 2 - there always exists factorization such that
(z)) = QV ; ( ... (( (1=1;; (((-)))
(C.53)
where Q is an orthogonal matrix, (+) is a column- matrix, and V(z;U) is defined as
V(2; U) (I - UUT) TUT= 2.
(C.54)
In Theorem C.7, we extends this theorem from causal systems to finite-length (but non-causal) ones. Theorem C.7 (Complete factorization for ID-paraunitary systems). Suppose that a paraunitary system (2)) is finite-length, i.e., it can be written as Σn, h h for some sequence (h(n), n
[-L, then it can be factorized in the following form:
H(z)= = -(; ((z; ((-
V(z ((Z
(C.55)
where Q an orthogonal matrix, U()) columu--rrthggnnl matrix, and V(z; U' is defined in Equation (C.54). Consequently, the paraunitary system H()) is parameterized by L L
matrices Q and U
24

---

Under review as a conference paper at ICLR 2022
Proof for Theorem C.7. Given non-causal paraunitary system (2), counterpart (z) such that (z) 2 (=) (This can be done by shifting the causal system backward by L steps, which is equivalent to multiplying af in the spectral domain). Since the causal system A admits a factorization in Equation (C.55), we can write the non-causal system H (=) as
always find causal
(²)) = ='QV(2> (=: (00))) ... V(= ;0Lt)))
(C.56)
Therefore, it suffices to show that for an orthogonal matrix Q and any column-orthogonall matrix Ü, we can always find another column-oree orthogonll matrix U such that
QV
U).
(C.57)
If the equation above true, we can set U(() Ú(-11- for l < 0 and U (((-L) for which will convert Equation (C.56) into Equation (C.55).
Now we start to prove Equation (C.57). Note that any column- cothoon-rthooonal Ô has a complement Ú
such that (Ū Ü] is orthogonal and I = 00 T + + We then rewrite Equation (C.57) as
=QV(2 Ú) =Q(T -Q(1-U0) +00
(C.58)
= Q(1 -QI--00 +00
(C.59)
-(I (I-QUUTQ + +QūUTQ==]Q
(C.60)
-UI-UUT +UUT2)0 2)Q
(C.61)
V)2
(C.62)
where in Equation (C.61) we set U = QÜ. This completes the proof.
C.3.2 MULTI- DIMENSSIMENIONNL (MD) PARAUNITARY SYSTEMS
If the data are multi lilli-ddmensional (MD), we will need MD-com covvolvlltii layers in neural networks. Analogously, we can prove the equivalence between orthogonal MD-convolutions in the spatial domain and MD- MD--parumitarry systems in the spectral domain, i.e.,
H(z) (()) I, (21, 2D), |aa 1, E [D],
(C.63)
where D is the data dimension. In this work, we adopt parameterization based on separable systems. Definition C.8 (Separable AD-paraunitary system). A MD-paraunitary system (z) is separable if there exists D ID-paraunitary systems H1 (HD) such that
((2)= = (21. ... zD) 2 (z) ... HD(zD).
(C.64)
Therefore, we can construct an MD- MD-paraunitary system with D number of ID-paraunitary systems, each of which is represented in Equation (C.55). Notice that not all MD-paraunitary systems are separable, thus the parameterization in Equation (C.64) is not complete (see Section 5 for discussion). However, we can guarantee that our parameterization realizes all separable MDpparaunttary systems each separable paraumitary system admits a factorization in Equation (C.64), where each 1D-system admits factorization in Equation (C.55).
C.3.3 INTERPRETATIONS OF PREVIOUS APPROACHES
In Theorem B.5, we have shown that paraunitary transfer matrix is both necessary and sufficient for a convolution to be orthogonal. Therefore, we can interpret all approaches for orthogonal convolutions as implicit constructions of paraunitary systems, including singular value clipping and masking (SVCM) (Sedghi et al., 2019), block convolution orthogonal parameterization (BCOP) (Li et al., 2019b), Cayley convolution (CayleyComv) (Trockman & Kolter, 2021), skew orthogonal convolution (SOC) (Singla & Feizi, 2021). Furthermore, we prove how orthogonal regularization (Wang et al., 2019; Qi et al., 2020) encourages the transfer matrix to be unitary for all frequencies.
(1) Singular value clipping and masking (SVCM) (Sedghi et al., 2019) clips all singular values of H (eld) to ones for each frequency after gradient update. Since the clipping step arbitrarily
25

---

Under review as a conference paper at ICLR 2022
enlarge the filter length, SVCM subsequently masks out the coefficients outside the filter length. However, the masking step breaks the orthogonality, as we have seen in the experiments (Section 6.1).
(2) Block convolution orthogonal parameterization (BCOP) (Li et al., 2019b) tries to generalize the spectral factorization of ID- p-paruuntarry systems in Equation (C.55) to 2D -aarauunitary systems.
(21, 22) 21
K-1
22
Q (21,20;; U1 UZ ... ((z 22: U (K-1) U,
(C.65)
where 22; (2 U/ ( Uf (2g: U In other words, this approach makes each V-block, instead of the whole paraunitary system, separable. This factorization in BCOP is incomplete for 2D- pD-aauunnty system - unlike 1D-paraunitary systems, not every 2D-parauniaary system admits factorized form (Lin & Vaidyanathan, 1996).
(2) Calyey convolution (CayleyConv) (Trockman & Kolter, 2021) aims to generalize the Cayley transform for orthogonal matrices in Equation (C.88) to 2D-paruunitary systems H 22):
H (11 22) = (1 A 22)) (1 + A(1 22))
(C.66)
where A(21, 22) is
matrix for |2] 1, |21 (i.e.,
A -بع ) for any w1,42) 42). Since Cayley transform cannot parameterize matrix with singu- lar value -1 for any frequency, the CayleyConv is not complete parameterization.
(4) Skew orthogonal convolution (SOC) (Singla & Feizi, 2021) aims to generalize the matrix exponential for orthogonal matrices (Equation (C.90)) to convolution exponential for 2D-paruunitary systems H 22);
A(21,22 22)
A(21,
H [21, (2,,, 22) = exp (1
(21, 22
I A (21, 22) +
+ (C.67)
k!
2
k=0
where A(21, 22) is skew-Hermitian matrix for any matrix for |2] = 1, |22 = 1 (in other words, A(e )²ع yt A A ف for any W1,42). It not resolved whether all 2D DD-paraunitary systems can be represented in terms of convolution exponential.
(5) Orthogonal regularization (Ortho-Reg) (Wang et al., 2019; Qi et al., 2020) is developed to encourage orthogonality in convolutional layers. We show that such orthogonal regularization equivalent to a unitary regularization of the paraunitary system with uniform weights on all frequencies.
Σ h|m]h(n Rd] T RE
8li]
H H (cdu)) (c
I1| du,
(C.68)
2x
SEZ
where 8[0] = I is an identity matrix, 8[n] O is zero matrix for n o O. We prove the equivalence
more generally in Proposition C.9. However, this approach cannot enforce exact orthogonality and in practice requires hyperparameter search for a proper regularizer coefficient.
Proposition C.9 (Parseval's 's theorem for ridge regularization). Given a sequence of matrices h (h[n), n Σ}, the following four expressions are equivalent:
1
H R
(clln)
'H HR (clw)
I
du,
(C.69a)
2x
hm] T h/nn Ri]- - -8[p]
(C.69b)
162
NEZ
1
H
R (elw) . (Rl (elwv) 1 dw,
(C.69c)
2x
Σ
Σ
h[]]h[n - Rd]
-5Ta]
(C.69d)
REZ
R
where || |||| denotes the Frobenius norm of a matrix.
26

---

Under review as a conference paper at ICLR 2022
Proof of Proposition C.9. We first prove the equivalence between Equations (C.69a) and (C.69c).
(clu) H [8] (ct))
[ (alw) 1 (clw) - -1 1) H Hlll (cll) - -1))
(C.70)
tr (H
(R] (ew))) H ((lw))) 2tr (H HI
+ (C.71)
H 1 (el ) ( 2tr (cbo) +1 (C.72)
(
(c -1) -1)
H (cdw) ) (dw)
(C.73)
H [2| ( ( r x||
(C.74)
where Equations (C.70) and (C.74) make use of ||| tr( Equations (C.71) and (C.73) are due to the linearity of (r(),, and Equation (C.72) utilizes tr(AB) = tr(BA).
Next, we prove the equivalence between Equations (C.69a) and (C.69b).
Rl (elw) 180 (cl")) - -I Σ
Hrl HrlR(
(C.75)
TE.R]
Σ
Σ h2 [[m] 1 im - -8(1] -Ji
(C.76)
rE(R) 'EZ ME
h|Rm r] h[R(m + -dli]
jui
(C.77)
()
mEE
Σ mEZ
h|Rm + +r] h(Rm + Rij
81d]
jui
(C.78)
iEz
(E(R)
Σ h[m] AnE
h/m Rd] 8[i]
e-ii
(C.79)
EZZ
where Equation (C.75) follows from the definition of polyphase matrix in Equation (C.15). Equa- tion (C.76) uses a number of properties Fourier transform: a Hermitian in the spectral domain is a transposed reflection in the spatial domain, frequency-win wise multiplication in the spectral domain is a convolution in the spatial domain, and an identical mapping in the spectral domain is an impulse sequence in the spatial domain. Equation (C.77) follows from the definition of polyphase components in Equation (C.7), and Equation (C.79) makes change of variables n = Rm + In summary, we show that the LHS (denoted D D(el") is Fourier transform of the RHS (denoted as dii):
H| (elur) (cl)
Σ
Σ hm]]]
h(mn Ri) [[[]]]]]
e -us
(C.80)
((ele)
nEZ
di
Applying Parseval's theorem (Theorem B.3) to the sequence d = [dli), E Z}. we have
H [T] (clw)) (1 H
1| dw = Σ Σ hmn
h/n Ri]
5li]
(C.81)
2TT
iEZ
REZ
which proves the equivalence between Equations (C.69a) and (C.69b). With almost identical argu- ments, we can prove the equivalence between Equations (C.69c) and (C.69d), that is
H
[1] (c H
H
(clu)t -1 1|2dw di Σ SE2
11
h|n]h(n Ri Σ meZ
81i]
(C.82)
2T
which completes the proof.
27

---

Under review as a conference paper at ICLR 2022
Table 5: Computational complexities of different approaches for orthogonal convolutions.
Approach
Computational Complexity
Normal
O CL O + CN O + LAC2)
SVCM
Ortho-Reg
CayleyConv
(oN NºC O O 0 (12N2 KIZC9)
SOC
BCOP SC-Fac
o O
In Table 5, we compare the computational complexities (forward pass) of orthogonal convolutions against normal convolution. For simplicity, we assume the feature maps have size x N, the convolution filters have size L L, and the maximum of input/output channels is C. We use K to denote the number of iterations for Björck's ' algorithm in BCOP, or Taylor's s series order in SOC.
For SC-Fac, BCOP, SVCM, or Ortho-Reg, the first term O(L2N2 is the base cost of a normal convolution, and the second term is the overhead for reconstruction, projection, or regularization. Note that the overhead in SC-Fac is comparable to Ortho-Reg Bego which is lower than SVCM or BCOP. C < N2, the overhead SC-Fac is negligible compared to the base cost.
For CayleyConv, the first term ( log ()))()) the cost for fast Fourier transform (FFT), and the second term ( is the cost for matrix inversion for all frequencies. The cost of SOC is exactly K times as a normal convolution. The computational complexities of CayleyConv and
SOC are significantly higher than the one of normal convolution.
For those approaches whose filters be explicitly obtained (SC-Fac, BCOP, SVCM, and Ortho- Reg), the inference time of an orthogonal convolution is no different from a normal convolution, i.e., ((L2 On the other hand, for those approaches whose filters are implicitly defined (CayleyConv and SOC), the inference time is the same as the forward pass in training.
C.4 CONSTRAINED OPTIMIZATION OVER ORTHOGONAL MATRICES
In Theorem C.7, we have shown how orthogonal matrices characterize paraunitary systems. Our remaining goal, therefore, is to parameterize orthogonal matrices using unconstrained parameters. In this part, we review popular parameterization methods: Householder reflections (Mhammedi et al., 2017; Mathiasen al., 2020), Givens rotations (Dorobantu et al., 2016; Jing al., 2017), Björck orthogonalization (Anil et al., 2019), Cayley transform (Helfrich et al., 2018; Maduranga et al., 2019), and exponential map (Lezcano- Casado & Martinez-Rubio, 2019; Lezcano Casado, 2019).
(1) Householder reflections (Mhammedi et al., 2017; Mathiasen et al., 2020). The parameteriza- tion represents an orthogonal matrix using product of Householder matrices. Given N N and E {1,.... N). we define H as mapping from vector R" (a scalar R for n 1) to
a blagk-diagonal matrix H (m)(()) E TR. NxN,
IN-D
[N-1
H (a)
H (()
(C.83)
I,
2
22 T0
where I, E Raxa denotes an identity matrix. For n 2 2, H (w) is the Householder matrix that represents the reflection with respect to the hyperplane orthogonal to concat(O v) E R and passing through the origin. For 1, the scalar takes values {-1, -1,. which makes (v) either an identity matrix (for 1) or Householder matrix (for -1). This method parameterizes orthogonal matrix as product of (())ss 's:
U H (m H (2) (
(C.84)
where each (r) IR is a learnable vector for > 2, and ( is fixed constant that is generated at initialization and fixed afterward. Observing that Equation (C.84) is serial (unfriendly to parallel computing), Mathiasen et al. (2020) proposes to increase its parallelism using WY transform.
28

---

Under review as a conference paper at ICLR 2022
(2) Givens rotations (Dorobantu et al., 2016; Jing et al., 2017). The parameterization represents special orthogonal matrix using a product of Given rotations matrices. Given N E and i, {1...., N with i o J. define G)6d) mapping from an angle 0 E IR the corresponding rotation matrix ((a,)) N
0
cos 0
sin A
Glf (0)
(C.85)
sin 0
cos
This method parameterizes a special orthogonal matrix U as a product of Gii's U- (000.)) (( ((0.2)(010.))) ((122)0(1.2) C(N-2,N (0(N--2N-11))
(C.86)
where g(id)ss are N(N 1) unconstrained parameters. Since the determinant of each rotation matrix is +1, their product U also has +1 determinant, thus special orthogonal matrix. Again, Equation (C.86) is highly serial, thus both Dorobantu et al. (2016) and Jing et al. (2017) propose to group N/2 Given rotations into packed rolation to increase the parallelism.
(2) Björck orthogonalization (Anil et al., 2019). The algorithm was first introduced in Björck & Bowie (1971) to compute the closest orthogonal matrix of given matrix. Given initial matrix Un. this algorithm iteratively approaches its closest orthogonal matrix as:
1 Ph +........ +...... (-1)² ( 2
U Ux I
PPP
vk E [K]
(C.87)
p
where K is the iterative steps, Pa = U UR. and p controls the trade-off between efficiency and accuracy at each step. When the algorithm is used for parameterization, it maps unconstrained matrix Un to an approximately orthogonal matrix UK in steps. Although Björck parameterization is complete (since any orthogonal matrix Q can be represented by Uo Q), it is inexact due to the iterative approximation.
(3) Cayley transform (Helfrich et al., 2018; Maduranga et al., 2019). The transform provides a bijective parameterization of orthogonal matrices without -1 eigemvalue with skew-symmetric matrices (i.e., A
AA)
U= (I- A)-1
(C.88)
where the skew-symmetric matrix A is represented by its upper-triangle entries. Since orthogonal matrices with -1 eigenvalue are out of consideration, the parameterization is incomplete. Helfrich et al. (2018); Maduranga et al. (2019) overcome this difficulty by a scaled Cayley transform:
U D(I A)(T A)
(C.89)
where D is a diagonal matrix with 1 non-zero entries, which is (randomly) generated at initialization and fixed during training.
(4) Exponential map (Lezcano-Casade & Martínez-Rubio, 2019; Lezcano Casado, 2019). The mapping provides a surjective parameterization of all special orthogonal matrices (with +1 determi- nant) with using skew-symmetry matrices (i.e., A =
AA)
A
1 A
U (A)
1 +
A
(C.90)
k!
2
k=
where the infinite sum can be computed exactly up to machine- machine-precision (Higham, 2009). Lezcano- Casado & Martinez-Rubio (2019) derives an efficient backpropagation algorithm for the mapping, making it an exact and efficient parameterization in neural networks. To support complete parame- terization for all orthogonal matrices, Lezcano Casado (2019) extends the mapping as:
U = Q exp(A)
(C.91)
where is an orthogonal matrix, which is generated at initialization and fixed during training.
In principle, we can use any of these approaches to parameterize the orthogonal matrices. In this work, choose exponential map due to its exactness, efficiency, and completeness.
29

---

Under review as a conference paper at ICLR 2022
D LEARNING DEEP ORTHOGONAL NETWORKS WITH LIPSCHITZ BOUNDS
In this section, we first discuss the properties of GroupSort and Lipschitz networks. Subsequently, we prove Proposition 4.1, which exhibits two approaches construct Lipschitz residual blocks. Lastly, we prove in Proposition D.I when a paraunitary system (represented by a complete factorization as in Theorem C.7) reduces to an orthogonal matrix. The reduction allows us to apply the initialization methods for orthogonal matrices to paraunitary systems.
GroupSort and orthogonality. The GroupSort activation separates inputs into groups and sorts each group into ascending order (Anil et al., 2019). It guarantees two properties: (1) The activation is norm preserving in the forward pass input vector. (2) The activation is gradient norm preserving in the backward pass a sorting function acts as permutation, which is orthogonal. GroupSort with the group size of two a spacial case that we use in the paper followed by (Chernodub & Nowicki, 2016; Anil et al., 2019).
sorting function does not change the norm of any
A Lipschitz network with orthogonal layers and GroupSort activations is locally orthogonal. Given any input x to the network, there exists a neighborhood Mzz r) with radius such that the sorting order in each activation does not change. In this neighborhood N (z,r). each GroupSort layer operates as constant permutation (thus orthogonal); consequently, the whole network is locally orthogonal.
Lipschitz residual blocks. In Proposition 4. 1, we prove the Lipschitzness of two types of residual blocks, one based on additive dkp--conectionn and another based on concatenative one (See Figure 6).
We first prove the Lipschitzness for the additive residual block f f(x) A (x) + (1 (x)) Let æ, x' be two inputs to f and f(x), f(x') be their outputs, we have [l(x=') f(=) || (af (a²) + (1 (1-o) (af +
Proof for Proposition 4.1.
(1-a)) fx)))
(D.1)
I (2') (1 ((-)
(D.2)
+ a1 [f(x)) - (a))
(D.3)
I aL |x' - x1| + (1)a)\lll -
(D.4)
= L x - x||.
(D.5)
where Equation (D.3) makes uses of the triangle inequality, and Equation (D.4) is due to the L.-
Lipschitzness of both / f². Therefore, we have shown that (a fax) s T.Ila' all.
Similarly, we prove the Lipschitzness for the concatenative residual block g g(x)
-
P Ig (a') ) g=*)) Let x. x' be two inputs to g and g(z). g(z') be their outputs, we have
I1g(=') g(x))]²
P [g (a: )= I9 (x'("")))) (=')) g=)(()))))))
(D.6)
|| (x0 )i
[g]
(=)))
(D.7)
|a')""") (z)
(D.8)
S L2 |a" x² ||
+ 1?
x²' x²
(D.9)
1 || |n'"" .0'1 [ar 2
la+;;
(D.10)
L || x=1?
(D.11)
where Equation (D.7) utilizes || = ||>||, Vaa, and Equation (D.9) is due to the L-Lipschitzness of
g². 92. The equations above implies that [|g(x") - g(x)) || < L||x' - -zll.
Reduction of a paraunitary system to an orthogonal matrix. In Proposition D.I, we prove a special case when a paraunitary system reduces an orthogonal matrix. The reduction allows to apply the initialization methods for orthogonal matrices to paraunitary systems.
Proposition D.1 (Reduction of a paraunitary matrix to an orthogonal matrix). Suppose a paraunitary system (z) takes the complete factorization in Equation (C.55), and assume L = L with U(-() =
QU for all f, then the paraunitary matrix H (z) reduces to an orthogonal matrix Q
H()) (2; (())))))........ V(:::( QV (U ())
V(= ((=-;:
Q (D.12)
30

---

Under review as a conference paper at ICLR 2022
Channel
Chande Spiit
Orho Cons.
Ortho Copv. (Staik= 2
Ontin. Cuns:
Ortho Comy. (Saike 2)
GroppSor
(Susde
Grouphort
CroppSan
Canr.
Groupoot
Onto Cons
Onho, Com
Untoo Conw
Orfho Com.
GregSon
GroupSert
I-a
Coneaterate
Add
AdM
Charnel Shuflle
Chanaol Skuffle
GroupSart
GcorpSont
(a) Basic additive block. (b) Strided additive block.
(c) Basic shuffling block. (d) Strided shuffling block.
Figure 6: Variants of residual blocks. In experiments, we combine (a) & (b) to construct an orthogonal ResNet, and (c) & (d) to construct an orthogonal ShuffleNet. In Proposition 4.1, we prove the Lipschitzness of these building blocks. Since composition of Lipschitz functions is still Lipschitz. it implies that a network constructed by these building blocks is also Lipschitz.
Proof for Proposition D.1. In order to prove Equation (D.12), it suffice to show that
V(z; (=
Q
(D.13)
and Equation (D.12) will reduce recursively to the orthogonal matrix Q. For simplicity, we rewrite U(-)) as L and Ul) as R, by which we have
QR (or R = Q T L) and we aim to prove
LVQV (= R) Q. By the definition of ((2..) in Equation (C.54), expand it as
V(z; V(z - R. = [ -I-LL") LL Q [
[I-RR'] RR x1
LL LI'QUI-RAA RR d-
(T- LL QQ(T )L(TT- RR + LL QRR +(I LL JQRR z-1 (D.14)
c(0]
c[1]
Therefore, will need to show that c[-1] = 0, c[1] 0 and c(0] = Q.
We first show that both cl- 1] for and c[1] for z are zero matrices.
dl-1| L RR
(D.15)
= .LL LL'Q-LL' LLLTLRRRR
(D.16)
= -LQQ - LLQ L) RR
-
(D.17)
LR R)R
(D.18)
LR -R =0
(D.19)
c[1 (I- LL
) QQRR
(D.20)
-RR LL QRR
(D,21)
= -QRRR - -LL (QR)R
(D.22)
LRR L)R
(D.23)
LR.. -RR =0.
(D.24)
31

---

Under review as a conference paper at ICLR 2022
Table Comparisons of various initialization methods on WidcResNet (kernel size 5).
Initialization
WideResNeelO-100
WideResNee12-100
Clean (%)
PGD (%)
Clean (%)
PGD (%)
uniform
83,58
73.20
87.55
75.71
torus
82.40
72.50
88.12
75.43
permutation
83.18
73.16
87.82
76.46
identical
83.29
73.49
87.82
75.49
Lastly, show that the constant coefficient c(0) is equal to Q-
c|0] = (I - LL
RR + LL T QRR
(D.25)
= - LL L -QRR +2LL QRR'
(D.26)
- LR -LR' +2LR =Q
(D.27)
which completes the proof.
E
SUPPLEMENTARY MATERIALS FOR EXPERIMENTS
E. EXPERIMENTAL SETUP
Network architectures. For fair comparisons, we follow the architectures by Trockman & Kolter (2021) for KW-Large, ResNet9, WideResNet10-10 100 (i.e., shallow networks). We set the group size for GroupSort activations as all experiments. For networks deeper than 10 layers, we implement their architectures modifying from the Pytorch official implementation of ResNet. It is crucial to replace the global pooling before fully-connected layers with an average pooling with a window size of 4. For the average pooling, we multiply the output with the window size maintain its 1 1-Lipschitzness. Other architectures, including ShuffleNet and plain convolutional network (ConvNet), are further modified from the ResNet, where only the skip- ceti-coonections are changed removed. We use the widen factor to indicate the channel number: we set the number of channels at each layer as base channels multiplied by the widen factor. The base channels are 16, 32, 64 for three groups of residual blocks. More details of the ResNet architecture can be found in the official Pytorch implementation.
Learning strategies. We use the CIFAR-10 dataset for all our experiments. We normalize all input images to [0, 1] followed by standard augmentation, including random cropping and horizontal flipping. We use the Adam optimizer with a maximum learning rate of 10-2 coupled with piece-wist wise triangular learning rate scheduler. We initialize all our SC-Fac layers permutation matrices: (1) we select the number of columns for each pair (+))) U((() uniformly from (1,- (1, T} at initialization (the number is fixed during training); (2) for > O, we sample the entries in (+) uniformly with respect to the Haar measure; (3) for O, we set (-F) = QU()) according to Proposition D.I.
E.2 ADDITIONAL EMPIRICAL RESULTS ON HYPER- PATEER-PAAMEEERS SELECTION
Multi-class hinge loss. Following previous works on Lipschitz networks (Anil et al., 2019; Li et al., 2019b; Trockman Kolter, 2021), we adopt the multi-class hinge loss in training. For each model, we perform a grid search on different margins eo E {1 10 33 2 x 10 3, 5 x 10-3, x 10 10-2,3 x 10 2.5 x 10 0.1, 0.2, 0.5) and report the best performance terms of robust accuracy. Notice that the margin 6o controls the trade-off between clean and robust accuracy, shown in Figure 7.
Initialization methods. Proposition D.I. we have shown how initialize our orthogonal convolu- tional layers as orthogonal matrices. In Table 6, we perform study on different initialization methods, including identical, permutation, uniform, and torus (Henaff et al., 2016; Helfrich et al., 2018). We find that permutation works the best for WideRessNe12-110 while all methods are similar in shallower WideResNet10-10. Therefore, we use permutation initialization for all other experiments.
Phttps://// //tta::///hhbt httphuu...oo/ptoooccccooooo htwp:///w...tttioo//////////tttt in
32

---

Under review as a conference paper at ICLR 2022
100
Train
Test
PGD
Accuracy (%)
500
200 100
2
Margin (x10-3)
Figure 7:
Effect of the Lipschitz margin En for WideResNet22-10. It shows trade-off' between clean and robust accuracy with different margins for multi-class hinge loss. As shown, the training and test accuracy become higher with larger margin, but the robust accuracy decreases after eg = 0.1.
Table 7: Comparison of different depth and width on WideResNet (kernel size 5), Some numbers are missing due to the large memory requirement (on Tesla V100 32G). The notation width factor indicates (channels base channels factor).
10 layers
Width
8
10
10
Clean (%)
PGD with
36/255 255 (%)
Ours
79.96
84.17
84.96
84.61
84.09
65.92
69.70
72.18
72.51
74.29
Cayley
77.88
82.14
82.56
85.53
85.01
66.65
73.06
74.33
75.66
76.
RKO
81.37
83.55
84.67
85.18
84.62
70.55
74.44
76.41
76.65
77.02
22 layers
Width
8
10
10
Clean (%)
PGD with
36/255 (%)
Ours
79.90
82.22
87.21
88.10
87.82
67.95
70.88
74.30
75.12
76.46
Cayley
79.11
84.82
85.85
69.79
65.61
74.81
RKO
82.71
84.19
84.33
84.55
72.40
74.36
75.66
76.41
34 layers
Width
6
8
10
3
8
10
Clean (%)
PGD with
36/255 (%)
Ours
81.24
88.
88.92
69.21
71.85
75.09
Cayley
82.46
84.29
71.27
74.73
RKO
81.51
83.24
83.92
71.38
73.84
75.03
Network depth and width. Exact orthogonality is criticized for harming the expressive power of neural networks, and we find that increasing network depth/width can partially compensate for such loss. In Table 7, we perform study on the impact of network depth/width on the predictive performance. As shown, deeper/wider architectures consistently improve both the clean and robust accuracy for our implementation. However, the best robust accuracy achieved by 22-layer network since afford a wide architecture for 34-layer architecture.
Comparison against normal convolutional networks. In Table 8, We perform a comparison between orthogonal networks and normal convolutional networks. Their architecture identical except for the activation function (GroupSort for ours and ReLU for normal convolutional networks). Since batch normalization is common in normal convolutional networks but not in Lipschitz networks,
33

---

Under review as a conference paper at ICLR 2022
Table Comparison of orthogonal convolutions and normal convolutions on WideResNet (ker- nel size 5). The notation width factor indicates (channels base channels x factor).
22 layers
Width
1
3
6
10
3
6
8
10
Clean (%)
PGD with e 36/255 (%)
Ortho. (SC-Fac)
79.90
82.22
87.21
88.10
87.82
67.95
70.88
74.30
75.12
76.46
Normal (w/o BN)
88.81
90.71
91.59
91.64
91.57
54.33
66.36
69.35
69.94
74.10
Normal (with BN)
88.52
91.74
91.20
92.29
92.40
51.53
66.90
73.18
73.89
73.02
Training (s)
Inference (s)
Ortho. (SC-Fac)
145.3
173.4
250.1
323.1
434.0
1.47
4.35
9.72
12.65
17.56
Normal (w/o BN)
13.77
30.71
69.35
99.94
153.5
1.01
3.03
6.77
9.12
13.03
Normal (with BN)
16.56
34.16
87.49
106.9
167.4
1.14
3.34
7.33
9.69
13.39
Table 9: Practical robustness against &oo adversarial examples (WideResNet kernel size 5, Loo perturbation radius of 8/255). BCOP+ and SOC (Singla & Feizi, 2021) results with ResNet-18 are reported by Singla & Feizi (2021).
Model
Method
Clean (%)
PGD (%)
BCOP+
79.26
34.85
Resnet-18
SOC
82.24
43.73
BCOP
77.57
46.35
WideResNet22-mant
Cayley
78.27
45.21
Ours
76.28
46.27
we provide both results for normal convolutional networks with or without batch normalization. In the table, we report the clean/robust accuracy, train time for epoch, and inference time for the test set.
Robustness against L. attacks using adversarial training. Since orthogonality only guarantees & Lipschitzness, Lipschitz networks with orthogonal layers are not naturally robust to foo perturbations. To further guard Lipschitz networks against loo attacks, we follow the approach of adversarial training in Wong et al. (2020). For training, we use 50 PGD iterations with step size 2/255 and 10 random restarts. We report the experimental results in Table 9. We observe that different orthogonal convolution methods achieve similar loc robustness on WideResNet-22. Furthermore, the Lipschitz networks with WideResNet22 architecture consistently better than ResNet-18, which is previously used in Singla & Feizi (2021).
FGSM variant with step size 10/255; for evaluation,
E.3 ON THE NECESSITY OF EXACT ORTHOGONALITY
Due the benefits like generalizability and robustness, achieving exact orthogonality in convolutions is the primary goal of a current research line (Sedghi et al., 2019; Li et al., 2019b; Trockman & Kolter, 2021; Singla & Feizi, 2021). However, until our work, no previous approach achieves orthogonality up to machine precision. Therefore, our proposed method serves as an extreme case in gaining insight into the trade-off between orthogonality and expressiveness.
In Section 6, we have seen that exact orthogonality is not critical in shallow Lipschitz networks for robustness, and various orthogonal convolutions (with different precision) achieve comparable results. However, show the results in Table 7. indicates that exact orthogonality crucial in learning deep Lipschitz networks. However, without our implementation of exact orthogonality (which does not exist before), is unclear whether exact orthogonality up to machine precision is needed in Lipschitz networks.
method is more favorable in deeper networks (with more than 10 layers)
Moreover, exact orthogonality is essential for other important and timely applications. For example, reversible networks/normalizing flows (Kingma Dhariwal, 2018; Van Den Berg et al., 2018) require exact orthogonality compute inverse transform and determinants accurately.
34

---

Under review as a conference paper at ICLR 2022
F ORTHOGONAL CONVOLUTIONS FOR RESIDUAL FLOWS
In this section, we first review the class of flow-based generative models (Papamakarios et al., 2019; Kobyzev al., 2020). We focus on invertible residual network (Behrmann et al., 2019), a flow-based model that relies on Lipschitz residual block, and its extended version Residual Flow (Chen et al., 2019). We then show how to construct improved Residual Flow using our orthogonal convolutions.
Flow-based models. Given an observable vector æ E TR and latent vector 2 E R.D. we define bijective mapping f _DD + RD from the latent vector to observation = f(z). We further define the inverse of f as = f-, with which we represent the likelihood æ by the one of z as:
Inpx (x) (z) In/det JF(x)),
(F.1)
where Px is the data distribution, pz is the base distribution (usually normal distribution), and JE (x) is the Jacobian of F at æ. In practice, the bijective mapping o is composed by a sequence of K bijective mapping such that f fK ....o f1, where each fo is named as a flow. Since the inverse mapping F = F1 o..... Fx transforms the data distribution px into normal distribution pz. flow-based models are also known normalizing flows. Accordingly, rewrite Equation (F.1)
Inpx (z) = In pz)) In det Jr, (2:),.
(F.2)
In practical flow-based model, we require efficient computations of (a) each bijective mapping fx. (b) its inverse mapping FA = f=² 1, and (c) the corresponding log- -og-determinant In/det J-(-)).
Invertible residual networks (i-ResNets). Behrmann et al. (2019) proposes flow-based model based on residual network (ResNet). Note that a block in ResNet is defined as F(x) x + g(x), where is convolutional network. In (Behrmann et al., 2019), the authors prove that F is a bijective mapping if g is I-Lipschitz, and its inverse mapping can be computed by fixed-poin point iterations:
1++1 y g(ak))
(F.3
where y y(ar) is the output of F and the initialization of the iterative algorithm is 20 = y. From the Banach fixed-point theorem, we have
x - 2xll22 = Lip Lip(g)
|2] -zell,
(F.4)
ie., the convergence rate is exponential in the number of iterations and smaller Lipschitz constant will yield faster convergence. Furthermore, the log-determinant can be computed as:
In (x: In pz(z)>) + tr (In (T + (z()))
(F.5)
(-1)==
-1) + tr
k [)(())
(F.6)
where the infinite sum is approximated by truncation and the trace is efficiently estimated using the Hutchinson trace estimator tr(A)= Ev=>((o,)) Av).
To constrain the Lipschitz constant, i-ResNet uses spectral normalization on each linear layer in the block. Moreover, to improve optimization stability, i-ResNet changes the activation function from ReLU to ELU, ensuring nonlinear activations have continous derivatives.
As summarized in the conclusion of Behrmann et al. (2019), there are two remaining problems in this model: (1) The estimator of the log-determinant is biased and inefficient; (2) Designing and learning networks with Lipschitz constraint are challenging - one needs to constrain each líncar layer in the block instead of being able to control the Lipschitz constant of a block.
Residual Flow, Chen al. (2019) address problem {(1) by proposing an unbiased Russian roulette estimator for Equation (F.6):
(-1)* v (z) V
tr (In (I + Jz(z))) En,v
(F.7)
k
P(N 2 k)
35

---

Under review as a conference paper at ICLR 2022
Table 10: Comparisons of various flow-based models on the MNIST dataset. We report the
performance in bits per dimension (bpm), where smaller number indicates better performance.
Model
MNIST
Glow (Kingma & Dhariwal, 2018)
1,05
FFJORD (Grathwohl et al., 2018)
0,99
i-ResNet (Behrmann al., 2019)
1.05
Residual Flow (Chen et al., 2019)
0.97
SC-Fac Residual Flow (Ours)
0.896
where n ~ p(N) and v ~N, I). Residual Flow further changes the activation function from ELU to LipSwish. The LipSwich activation avoids derivative saturation, which occurs when the second derivative is zero a large region. However, problem (2) remains unresolved.
Residual flows with orthogonal convolutions. We propose to address problem (2) by replacing the spectral normalized layers by orthogonal convolutional layers (SC-Fac). Note that orthogonal convolutions directly control the Lipschitz constant of a ResNet block. We keep all other components LipSwish activation instead of GroupSort, as GroupSort suffers
unchanged- in particular, from derivative saturation. We experiment our model on MNIST dataset. As shown in Table 10, our model substantially improve the performance over the original Residual Flow. We display some images generated by our model in Figure 8
7
7
5
3
X
}
e
5
5
1
b
7
3
4
4
6
1
Figure 8: Random samples from SC-Fac Residual Flow trained on MNIST.
36


Reviews:
[{"review_id": "_-w04mPP5iX", "reviewer": "Reviewer_EX1P", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This work proposes a new method for orthogonalizing the convolutional layers by exploring the equivalence between spatial orthogonal and spectral paraunitary. The experiments are conducted on various networks including the shallow KW-large networks and slightly deeper WideResNet22. Although the reviewer does not check the submitted code in detail, the code is well-written and clearly commented. \nThe major concerns are (1) the work seems to have made some overstatement of the contributions, claiming that all the previous work are heuristic, and the proposed approach is systematic with theoretical justification. The reviewer does not quite buy this point, and better explanation on this is needed; (2) the experimental results are not consistently showing the advantages of the proposed method, also the improvement in terms of computational efficiency seems to be marginal.\n\nBelow are some more detailed comments.\n\n1. The reviewer found the implementation of the proposed method somewhat hard to follow, it could be better to incorporate an algorithm view of the method to clearly present it. \n\n2. In the paper, the Q matrix is defined as an orthogonal matrix that is randomly initialized and fixed during training. But the reviewer didn’t find the associated implementation in the code (correct me if I missed anything), so the reviewer is wondering how the Q matrix is constructed in the experiments.\n\n3. When demonstrating the results of adversarial robustness, the paper devotes to $\\ell_2$ norm based attacks. The reviewer is curious about the results of  $\\ell_\\infty$ based attacks. \n\n4. The reviewer notices that in the code, when considering striding, the authors include 2 use cases [stride_wide, stride_slim], the reviewer is curious about the actual definition of the different use cases. Besides, the code of the proposed method mentions that the kernel size should be a multiple of stride (in the stride_wide case, this constraint is bypassed by letting kernel_size = kernel_size * stride), the reviewer would appreciate it if this part is presented in more detail. (An algorithm for handling different cases would be nice). \n\n5. This paper is missing quite a few citations on related work:\n\nhttps://arxiv.org/abs/1810.09102\n\nhttps://arxiv.org/abs/2103.00673\n\nhttps://arxiv.org/abs/1911.12207\n\nhttps://arxiv.org/abs/1905.11926\n\nPlease refer and discuss the relationship", "summary_of_the_paper": "This work proposes a new method for orthogonalizing the convolutional layers by exploring the equivalence between spatial orthogonal and spectral paraunitary. The work then empirically demonstrates the effectiveness of the proposed methods by comparing (1) the Lipschitzness (2) the results of adversarial robustness and (3) the time and memory cost among different methods. \n", "summary_of_the_review": "The paper is well-presented overall. However, better positioning of the work, and more convincing experimental results are needed.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "VyXBv5jiGp", "reviewer": "Reviewer_5fbR", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper proposes a nice framework which covers different orthonormalization methods for convolutional kernels. In the analyses, the proposed framework performs on par with the state-of-the-art.\n\nHowever, there are several issues with the paper. In general, first, some of the claims should be revised since they are not verified in the analyses. Second, experimental analyses should be improved with additional analyses on additional datasets and tasks in comparison with the other state-of-the-art methods.\n\nMore detailed comments are given as follows:\n\n1. The paper states that “However, many previous approaches are heuristic, and the orthogonality of convolutional layers is not systematically studied.” However, there is a nice literature on orthogonal CNNs, which explores these CNNs from various aspects including generalization and convergence properties of models, in various tasks including image recognition, speech processing and NLP, including adversarial robustness studied in this paper. Then, could you please describe the systematic study referred to and proposed in this paper, which is not covered in the literature?\n\n2. Please explain the statement “There are mature methods that represent orthogonal matrices via unconstrained parameters.” How does this enable to optimize parameters of orthogonal convolutions using standard optimizers instead of optimizers designed for optimization on orthogonal convolutions?\n\n3. There are some issues with the definition and interpretation of orthogonal layers. First, an orthogonal layer is defined according to preservation of norm of input and output. This can be achieved using different types of parameters of convolutions, even with scaled Gaussian parameters. In addition, orthogonal convolutions proposed in the literature satisfy some particular orthogonality properties of matrices of parameters. Second, the orthogonal convolution proposed in this paper is associated with paraunitary property of the transfer matrix.\n\n4. In the experimental analyses, in most of the results, state-of-the-art outperforms the proposed method, while in some results, the proposed method outperforms them. To show a more clear benefit of the proposed method over the state-of-the-art, could you please perform analyses on additional larger scale datasets such as Imagenet? Could you please also compare the proposed method with the methods which employ orthogonal matrices?\n\n5. It is proposed that “related works proposing orthogonalization methods do not guarantee Lipschitzness after training”. However, the proposed orth. conv. employ deep Lipschitz networks to guarantee Lipschitzness. If the proposed orth. conv. does not employ deep Lipschitz networks, then does it  guarantee Lipschitzness? \n\n6. How do you optimize “learnable (column)-orthogonal matrices”?\n\n7. While training models, how do you estimate and optimize h[z], H[z], ortho. Factors, and model params? In the code, Adam is used to optimize parameters. However, it is not clear how orth. factors are also optimized. Do you also optimize them using Adam?\n\n8. How do you apply z-transform on input, kernel and output. For instance, if an input NxN image x is convolved with a 7x7 kernel h, then how do you apply z transform on x and h? That is do you apply path wise or holistically? Also, if x’ is a feature map of size CxWxH, where C is the number of channels, W and H are weight and height of the map, then how do you apply the z-transform on the map?\n\n9. How do you compute ortho. factors efficiently?\n\n10. How do you calculate model parameters A?\n\n11. In the experiments, the proposed methods perform similar to the state-of-the-art. To show superiority of the methods in comparison with the state-of-the-art, additional analyses on larger scale datasets and models should be provided.\n", "summary_of_the_paper": "This paper suggests a framework for designing orthogonal convolutions using paraunitary systems. The proposed framework studies orthogonalization of different convolution operations. The proposed methods were examined on several datasets in comparison with state-of-the-art orthogonalization methods.", "summary_of_the_review": "The proposed framework is nice, and the initial results are promising. However, there are various unclear parts in the paper. In addition, some of the claims are not verified and experimental analyses are limited. Therefore, the paper should be improved with additional analyses and in detail revision for clear acceptance.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "TIS9iLKoxm7", "reviewer": "Reviewer_rQN6", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Orthogonality is an important problem in the design of neural network architecture that relates to many fundamental properties of the network such as trainability, generalizability and robustness. While the study of orthogonality in fully connected layers (or convolution layers with 4D kernels treated as 2D matrices) has a long history, it is only until very recent (in the past 2-3 years) that work on orthogonality of *convolution* layers emerges. This paper provides a solid study in this area by providing a method of enforcing orthogonality in convolutions, revealing its technical connections with previous methods, designing a deep residual Lipschitz network architectures and conducting solid experiments. I find the presentation to be mostly clear and easy to follow, though I feel that there is a tendency of overclaiming the contribution in the abstract & intro, see below.\n\n- Complete parameterization of orthogonal convolution. The paper claims that it offers a complete parameterization of orthogonal convolution, but this is not really the case. As stated in Sec. 2, it only offers complete design for *separable* orthogonal 2D convolutions. This puts the technique in an unfavorable position compared to previous methods that does not require separability (e.g. Trockman & Kolter). \n\n- \"Orthogonal Networks\". The paper frequently use the phrase \"orthogonal networks\", but it is not clear what that term entails. For example, it is claimed that \"Our versatile framework, for the first time, enables the study of architecture designs for deep orthogonal networks\", which seems an overclaim since orthogonality in neural networks have already been extensively studied before. In addition, if \"orthogonal network\" means that the entire network is an orthogonal transformation, then this is kind of a useless network since orthogonality implies linearity (as long as it is surjective). If it means approximately orthogonal then it should consider, in addition to the convolutional layers, the effect of the nonlinear layers - right now there is no discussion of whether the GroupSort that is used as the nonlinear layer is approximately orthogonal or not. \n", "summary_of_the_paper": "This paper presents a method for enforcing strict orthogonality of convolutional layers, by means of a factorization in the spectral domain. It shows that the technique can be extended to dealing with practical convolutions with strides, dilations and groups. The experiments demonstrated the superior performance in terms of adversarial robustness.", "summary_of_the_review": "Solid work on orthogonality of convolution, though there seem to be some overclaiming / imprecise statements in the intro/abstract that may be misleading. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "Mb5k3rEcIKH", "reviewer": "Reviewer_yYMs", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Strengths**\n- The proposed method is theoretically grounded and relatively efficient in computations.\n- The analysis of strided, dilated convolution layers is inspiring. \n- Numerical evidence on orthogonality evaluation of different designs for standard convolution shows that exact orthogonality is achieved.\n\n**Weaknesses**\n- It is nice to see that exact orthogonality is achieved however it remains unclear exact orthogonality is actually helpful or needed. For example, from Table 2, the proposed SC-Fac achieves the most \"accurate\" orthogonality result in worse performance in both certified and practical robustness. Even though the author claims that the method achieves \"comparable\" results with other baseline methods, the results are consistently worse than the baselines.  \n\n- The authors can compare their core idea with related work that is more heuristic, such as [1] which also considers achieving orthogonality in the spectral domain, as well as [2],[3].\n\n[1] Liu et al. Convolutional Normalization: Improving Deep Convolutional Network Robustness and Training\n\n[2] Wang et al. Orthogonal Convolutional Neural Networks\n\n[3] Bansai et al. Can We Gain More from Orthogonality Regularizations in Training Deep CNNs?\n\n- Even though the method is more computationally efficient, it is only compared with methods such as Cayley which is known to be computationally heavy. The method is still much computationally heavier than the original networks. It would be nice to have an extra line in Figure 4 showing the train time of the ordinary network. ", "summary_of_the_paper": "This paper proposed a theoretical framework for orthogonal convolutional layers based on the equivalency of orthogonal convolution in the spatial domain and the paraunitary systems in the spectral domain. The proposed method parametrizes the orthogonal convolution layer as compositions of multiple convolutions in the spatial domain, resulting in exact orthogonality. The layers are also more memory and computationally efficient than most previous methods. ", "summary_of_the_review": "The proposed method achieves exact orthogonal convolutional layers through re-parametrization. The method is theoretically grounded and easy to understand. Numerical proofs are provided to show exact orthogonality is achieved by composing a sequence of learnable convolutions. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a method for parameterizing orthogonal convolutional layers that derives from paraunitary systems in the spectral domain and performs a comparison with other state-of-the-art orthogonalization methods. The paper argues that the approach is more computationally efficient than most previous methods and that the exact orthogonality is important to ensure robustness in some applications.

The reviewers had diverging opinions about the paper, with most reviewers appreciating the theoretical grounding and empirical analysis, but with some reviewers finding weakness in the clarity, reproducibility, and discussion of prior work. The revisions addressed many, but not all, of the reviewers' criticisms.

One point that was highlighted in the discussion is that the method is restricted to separable convolutions. The authors acknowledged this limitation, justifying the expressivity of the method with a comparison to CayleyConv (Trockman & Kolter) and a suggestion that more expressive parameterizations are not necessarily available in 2D. I am not sure this is entirely accurate. In the discussion of related work, the paper briefly mentions dynamical isometry and the prior work of Xiao et al. 2018, who develop a method for initializing orthogonal convolutional layers. What the current paper fails to recognize is that Algorithm 1 of Xiao et al. 2018 actually provides a method for parameterizing non-separable 2D convolutions: simply represent every orthogonal matrix in that algorithm in a standard way, e.g. via the exponential map. While I think there is certainly value in the connection to paraunitarity systems, it seems to me that the above approach would yield a simpler and more expressive representation, and is at minimum worth discussing.

Overall, between the mixed reviewer opinions and their lingering concerns and the existence of relevant prior art that was not discussed in sufficient depth, I believe this paper is not quite suitable for publication at this time.
Decision: Reject