Discriminative reconstruction via simultaneous dense and  sparse coding
Authors: Abiy Tasissa
Manos Theodosis
Bahareh Tolooshams
Demba E. Ba
Venue: Accepted by TMLR ()

Abstract: Discriminative features extracted from the sparse coding model have been shown to perform  well for classification. Recent deep learning architectures have further improved reconstruction  in inverse problems by considering new dense priors learned from data. We propose a
 novel dense and sparse coding model that integrates both representation capability and  discriminative features. The model studies the problem of recovering a dense vector x and  a sparse vector u given measurements of the form y = Ax+Bu. Our first analysis relies
 on a geometric condition, specifically the minimal angle between the spanning subspaces of  matrices A and B, which ensures a unique solution to the model. The second analysis shows  that, under some conditions on A and B, a convex program recovers the dense and sparse  components. We validate the effectiveness of the model on simulated data and propose a  dense and sparse autoencoder (DenSaE) tailored to learning the dictionaries from the dense  and sparse model. We demonstrate that (i) DenSaE denoises natural images better than  architectures derived from the sparse coding model (Bu), (ii) in the presence of noise, training  the biases in the latter amounts to implicitly learning the Ax + Bu model, (iii) A and B  capture low- and high-frequency contents, respectively, and (iv) compared to the sparse  coding model, DenSaE offers a balance between discriminative power and representation.

Published in Transactions on Machine Learning Research (8/2024)
Discriminative reconstruction via simultaneous dense and sparse coding
Abiy Tasissa Deportment of Mothematics
Tufls Universily
Emmanouil Thcodosis
dhhcodosis@g.harvan edu
School of Engineering and Applied Sciences
Horvard University
Bahareh Tolooshams
btoloosh@callech.cc edu
Computing + Mathematical Sciences
California Institute of Technology
Demba Ba
dembo @sens. www.wrd..aaaadd..oooo edu
School of Engineering and Applied Sciences
Harvard University
Reviewed on OpenReview: https: // openreview. net/ forum? id= FkgM06HEbb
Abstract
Discriminative features extracted from the sparse coding model have been shown to perform well for classification. Recent deep learning architectures have further improved reconstruction in inverse problems by considering new dense priors learned from data. We propose novel dense and sparse coding model that integrates both representation capability and discriminative features. The model studies the problem of recovering dense vector x and sparse vector u given measurements of the form y = Ax + Bu. Our first analysis relies on a geometric condition, specifically the minimal angle between the spanning subspaces of matrices and B, which ensures a unique solution to the model. The second analysis shows that, under some conditions on A and B, a convex program recovers the dense and sparse components. We validate the effectiveness of the model on simulated data and propose dense and sparse autoencoder (DenSaF)) tailored to learning the dictionaries from the dense and sparse model. We demonstrate that (i) DenSaE denoises natural images better than architectures derived from the sparse coding model (Bu), (ii) in the presence of noise, training the biases in the latter amounts to implicitly learning the Ax + Bu model, (iii) A and B capture low- and high-frequency contents, respectively, and (iv) compared to the sparse coding model, DenSaE offers a balance between discriminative power and representation.
1
Introduction
The problem of representing data linear mixture of components finds applications in many areas of signal and image processing (Bertalmio et al. 2003 Mallat & Yu 2010 Variational partial differential
equations (PDE) approaches in Aujol et al. (2003) and Vese & Osher 20033) develop an image decomposition model whereby a larget image is decomposed into piecewise smooth component (cartoon) and a periodic component (texture). Another approach posits that a desirable model should use multiple matrices, each capturing different structures the image; for example, 4 is a matrix modcling texture and 4 is a matrix modeling cartoon. Along these methods is Morpohological Component Analysis (MCA) (Elad al, 2005 which utilizes pre-specified dictionaries and sparsity prior the representation coefficients. In the

---

Published in Transactions on Machine Learning Research (8/2024)
simplest setting, an image y is modeled in MCA y Ek= Tyxg where 11. D2 are the pre-specified structured dictionaries capturing different morphologies of the image. The MCA model is then based on the idea that the sparsest representation of each component is attained in the pre-set dictionary component. In contrast to MCA which imposes sparsity for all mixture coefficients, the proposed model in this paper adopts a combination ion of smooth and sparse regularization.
Related motivating problems for representing data as a linear mixture are the background foregrouudd separation problem (Zhou et al.] 2012) and anomaly detection in images (Chang & Chiang 2002). In the former problem, widely used approach is the robust principal component analysis (RPCA) algorithm (Candès et al.) 2011) which is based on decomposing a data matrix into low rank (background) and sparse (Foreground) components. The latter problem, anomaly detection with images, arises in most manufacturing processes and methods based on decomposing the images into smooth and sparse components have been studied (Yan et al., 2017 Shen et al., ) however, to the best of the authors' knowledge, no theoretical analysis has been conducted for that decomposition. In addition, the sparse and smooth components in image anomaly detection are localized, inhibiting the generality of the model.
In this paper, we study model which decomposes signal or image in consideration into smooth part, sparse part, and noise. The prototypical form of our model is y = Ax Bu +e, e, where y E R" is the mcasured signal, Ax is the smooth component, Bu is the sparse component and e is the noise. The smooth component is generated from the dictionary A E _=x using a smooth coefficient x. In turn, the sparse component is generated from the dictionary B R=** using a sparse vector u. We use Tikhonov regularization (Tikhonov et al. (995) and l regularization to promote smoothness and sparsity, respectively. With that, the general non-noisy problem we study in this paper is
min UER
||xx| 12 + ||ul|1 subject to = Bu,
(1)
where G is the Tikhonov regularization operator. Here on, we refer to the model in ① as the dense and sparse coding problem. The word dense here refers to the smooth part and is used to emphasize that we do not require any sparsity.
Both MCA and the dense and sparse coding problem naturally lend themselves to and share a common theme with sparse coding and dictionary learning. Sparsity regularized deep neural network architectures
have been used for image denoising and discriminative tasks such as image classification (Simon & Elad 2019:
Tolooshams et al. 2020 Rolfe & LeCum 2013). Recent work has highlighted some limitations of convolutions
sparse coding (CSC) autoencoders and its multi-layer and deep generalizations (Sulam et al.] 2019 Zazo et al. 2019) for data reconstruction. The work in Simon & Elad (2019) argues that the sparsity levels that CSC allows can only accommodate very sparse vectors, making unsuitable to capture all features of signals such natural images, and propose to compute the minimum mean-squared error solution under the CSC model, which is dense vector capturing richer set of features. Moreover, the majority of CSC frameworks subtract low-frequency components of images prior to applying convolutional dictionary learning (CDL) for reprosentation purposes (Garcia-Cardona & Wohlberg 2018); however, this is not desired for denoising tasks where noise corrupts low frequencies in addition to the high spectrum. The goals of the paper are twofold. First, it presents a theoretical analysis of the dense and sparse coding problem. Second, we argue the dense representation x in a dictionary A is useful for reconstruction and the sparse representation u has discriminative capability,
1.1 Organization of paper
2 discusses related work. In Section 3 we give some technical background to the main analysis. Section presents the theoretical analysis of the paper. Phase transition, classification, and denoising experiments appear in Section 5 We conclude in Section 6. We start by defining notations.
Section
1.2 Notation
Lowercase and uppercase boldface letters denote column vectors and matrices, respectively. Given a vector E R and support set S {I,...,,) n); Xs denotes the restriction of x to indices in S. supp(x) denotes
2

---

Published in Transactions on Machine Learning Research (8/2024)
the support of vector, defined supp(z) {i:: 24 + 0}. Given set S, S denotes its complement. For matrix A E Rmxp, As is a submatrix of size m x |S| with column indices in S. The column space of a matrix A is designated by Col(A), its null space by (e).A), We denote the Euclidean, lo, ε and Eoo norms of a vector x, respectively as |x||2- ||x||o. ||x||2, and ||x|oc The operator and infinity norm of a matrix A are respectively denoted as ||||| and || The sign function, applied componentwise to a vector x, is denoted by sgn(x)) The indicator function is denoted by 1. The column vector e; denotes the vector of zeros except a at the i-th location. The orthogonal complement of a subspace W denoted by W The operator Pw denotes the orthogonal projection operator onto the subspace W. log(z) denotes the logarithm of x in base e. ( denotes the direct sum of subspaces. F(X) denotes the expectation of a random variable X.
2 Related work
2.1
Compressive sensing from union of dictionaries
The dense and sparse coding problem is similar in flavor to sparse recovery in the union dictionaries (Donoho
& Stark 1989: Donoho & Huo 2001 Elad & Bruckstein 2002 Donoho & Elad 2003 Kuppinger al. 201 p.
Consider sets of orthonormal bases, A Rmxm and B E Rm in R One setting is based on the idea that given signal will have sparse representation with respect suitably predefined A or B (Mallat
1999:
Daubechies 1992 Dobson & Santosa 1996). The concept of the union of bases is based constructing an overcomplete dictionary [A B] from A and B. This model then posits that a signal y can be represented as = Ax + Bu, where x and u are sparse. Notably, the signal may not be individually sparse with respect to A and B, but it has sparsity in the joint representation (Elad & Bruckstein 2002: Donoho & Huo 2001). In Donoho & Stark (1889), the authors apply this model to error-correcting encryplion and the separal ion of two signals. In both cases, the measured signal is assumed to be a superposition of two components, each sparse in predefined dictionary. Most results in the literature of union of bases take the form of an uncortainty principle that relates the sum of the sparsity of x and u to the mutual coherence between A and B, and which guarantees that the representation is unique and identifiable by & minimization. In Donoho & Stark (1989,, the authors study the problem of recovering x and from Ax + Bu, where A E mm is a discrete Fourier matrix (DFT) and B E Rm*x is the identity matrix. Therein, under the assumption that the support of u is known, the result shows that x can be exactly recovered if [|o/|///l) < m. This result. for the Pourier-identity, pair was further generalized to the case where A and B are orthonormal bases (Elad & Bruckstein] 2002) and when the measurements come from a union of non-orthogonal bases (Donoho & Elad 2003 Kuppinger et al. 2011). We remark that all the aforementioned results assume sparsity on both X and 11
2.2 Error correction
The problem of recovering a signal x given the measurement model Ax + u, where is sparse error vector, is known as the sparse error correction problem (Candes et al. 2005). The work therein considers a tall measurement matrix A and assumes that the fraction of corrupted entries is suitably bounded. To obtain a sparse minimization program, the matrix A is eliminated by a matrix B, where BA = 0, resulting By Bu. The resulting model is then solved via E minimization and exactness is shown under the restrictod isometry condition
B. The works in Wright & Ma (2010); Nguyen & Tran (2013); Pope et al. (2013); Studer et al. (2011): ; Studer & Baraniuk (2014) study the general error correction problem y Ax + Bu under different models of the signal x, the sparse interference vector u and the matrices A and B.
We note that all the aforementioned works consider a single sparsifying norm to recover the components x and u. In contrast, we use mixed norms that impose the Tikhonov and sparsity regularization. We also note that when A has more columns than rows, one of the settings we consider in this paper, our problem departs from the sparse error correction problem.
2.3 Weighted Lasso
When there is some prior on the support of the underlying sparse vector u given measurements of the form y Bu, the works in Lian et al. (2018); Mansour & Saabl (2017) Vaswani & La 2010 : Oymak et al. 2012
3

---

Published in Transactions on Machine Learning Research (8/2024)
Friedlander et al. (011 Flinth 2016) consider weighted Lasso program. Assume that the estimate of the The standard weighted Lasso considers the following optimization program
support of is T C (1. (1.....)
n).
min ||u||2,0 subject to y= =u,
where lu/l1.w = Ei=1 wpy and w E R" indicates the vector of weights. For instance, Mansour & Saab (217)) set the weights as follows: w, [0,1] if i T and otherwise. The aforementioned works discuss the recovery of the underlying signal using weighted Lasso under some conditions on the weights, size and accuracy of the estimated support. One approach for the feasibility constraint in ( is to reformulate it as a weighted Lasso problem in a combined dictionary [A BJ where the support estimate is the support of x. This formulation has few limitations. First, the recovery guarantees in weighted Lasso require accuracy of the estimated support which would depend on the number of columns of A. Second, these guarantees impose uniform structure on the combined dictionary, such as the weighted null space conditions, whereas our conditions allow deterministic dictionary A and random dictionary B. Finally, even in the regime where weighted Lasso might succeed in recovering the underlying x and u, it does not guarantee that Ax is smooth as that regularization is not reflected in the Lasso optimization.
2.4 Morphological component analysis (MCA)
Morphological Component Analysis (MCA) considers the decomposition of signal or image into different components with each component having a specific structure (morphology) (Starck et al. 2004 2005 Bobin et al. 2007 Elad et al., 2005). In MCA, the specific structure is imposed via sparsity with respect to pre- specified dictionarics. Specifically, given K dictionaries {$I,.., 4x). we model the data y as a superposition of K linear components as follows: y y - b,y; where y; is assumed to be sparse in 4. but it is not as sparse (or not sparse at all) in other dictionaries. With this set up, the dictionaries discriminate between the different components. In Starck ct al.] (2004) a basis pursuit approach to solve the MCA is employed and its utility is demonstrated in examples such as separating texture from the smooth part of an image. The main difference of our model from MCA is a smooth-sparse decomposition as opposed to sparse-sparse decomposition with pre-set dictionaries that contain information about targeted morphologies. The theory and analysis of the two models is also markedly different as consider smoothness regularizer.
2.5 Dictionary learning and unrolling
Given a data set, learning dictionary in which each example admits a sparse representation is useful in a number of tasks (Aharon et al. 2006 Mairal et al. 2011). This problem, known sparse coding (Olshausen) & Field 1997) or dictionary learning (Agarwal et al. 2016 Garcia-Cardona & Wohlberg, 2018), has been the subject of investigation in recent years in the signal processing community. A growing body of work, referred to as algorithm unrolling (Monga et al. 2021), has mapped the sparse coding problem into encoders for sparse recovery (Gregor & Lecun 20100. In this paper, we unroll the dense and sparse coding problem for a principled design of an autoencoder. The designed autoencoder efficiently learns a dense representation x, useful for reconstruction, and a sparse representation u with discriminative capability.
2.6 Contribution
We focus on ( and start by first providing theoretical guarantees for the feasibility problem y = Ax+Bu. Our first result is basod on goometric condition on the minimum principal angle between certain subspaces. Next, we prove that the convex program in (1) recovers the underlying components x and u under some assumptions the measurement matrices and the Tikhonov regularizer. We empirically validate the effectiveness of our methods through phase transition curves and make a direct comparison to noisy compressive sensing, highlighting the latter's inability to recover signals adhering to our proposed model. We then apply our optimization ion algorithm to sense real data and validate the expected properties of the sparse and smooth components.
We connect the proposed model to dictionary autoencoder (DenSaF). We demonstrate the superior discrininative and representation capabilities of DenSaF.
unrolling by proposing a dense and sparse
4

---

Published in Transactions on Machine Learning Research (8/2024)
compared to sparse coding networks in the task of reconstruction and classifying MNIST dataset. In this task, we characterize the role of dense and spanse learned components; argue that the dense representation x is useful for reconstruction and the sparse representation u has discriminative capability. Moreover, for image denoising, we show that DenSaE outperforms other networks which are based only on sparse coding,
3 Technical background
We start by briefly reviewing uniqueness results for compressive sensing with exact measurements. The typical assumption in these analysis to assume the measurement matrices satisfy certain conditions such as the restricted isometry property (RIP) and coherence. our setting, we employ RIPless recovery analysis (Caness Plan 2011 Kueng Gross 2014), which will be referred and used in the proof of Theorem We note that existing anisotropic analysis based a single measurement matrix. For model, the anisotropic analysis is applied to certain matrix derived from A, B and the Tikhonov regularizer G.
3.1 Compressive sensing with exact measurements
An underdetermined linear system y Bu where y E I and B R=xa with n > generally has infinitely many solutions. One prior for the recovery of the solution is sparsity of the underlying vector This leads to the following optimization problem
min
|uu/o subject to Bu.
While (2 is a natural program, it is known to be computationally intractable. Common altcrnatives are basis pursuit. (BP) (Tropp 2004 Chen el al.] 2001) and iterative greedy methods such as orthogonal matching
pursuit (OMP) Davis et al. 1997 Pati al. 1993 Tropp & Gilbert] 2007). In basis pursuit, (2) is modified by considering convex relaxation of the to norm leading to the & minimization problem.
min WER"
|uu| subject to y Bu.
A fundamental question is under what conditions the above optimization program identifies the underlying solution for ( A related part of this question when the lo minimization problem admits a unique solution. One condition is the restricted isometry property (RIP) (Candes & Tao 2005p. The s-restricted isometry constant of an measurement matrix B the smallest constant 8, such that
5%) |u)l < |Bul| < (1 (1+ 6.)l[l
holds for all s-sparse signals u (an s-sparse vector has most non-zero entries). Small RIP constants ensure unique solution of the to minimization problem and further provide the guarantee that the & relaxation in (3) is exact (Candes] 2008). It is known that random measurement matrices have small RIP constants [Candes & Tao 2006; Baraniuk et al. 2008). Another condition for analysis is based on the coherence of measurement matrix B defined as
= max bb"byl $fj
where b, denotes the i-th column of B which is assumed to be unit-norm. To state the next result, consider = Bu", where u" is the underlying sparse vector. If ||u" ll < 2 1/ the &n problem admits a unique solution and both BP and OMP relaxations are exact (Donoho & Elad 2003 Gribonval & Nielsen 2003 Tropp 2004). We note that coherence conditions are typically st.oonger than those based on the restricted isometry property, specially for random matrices.
3.2 Compressive sensing with structured random matrices
We review the technical results Candes & Plan (0011 Kuong Gross (2014) which consider conditions for the exact recovery of the & minimization problem for the setting of structured measurement matrices. this setting, do not assume restricted isometry property (RIP) of the measurement matrices (Candes & Tao
5

---

Published in Transactions on Machine Learning Research (8/2024)
2005) and this broadens the sensing matrices that can be employed. We consider sequence of i.id. random vectors bi.... bn drawn from some distribution F on IR" and with measurements defined as = bb'u". u². Two properties are essential to the analysis. The first is the isotropy property which states that 4'bb²] for b O.F. The second property is the incoherence property. The incoherence parameter the smallest number F(F) such that
S p(F),
max 1
holds almost surely for any b F. Given these assumptions, the work in Candes & Plan 2011 provides the following theoretical result.
Theorem 1 (Cnndes & Plan 2011 Let B
vm E e,b, be measurement malrix and let be a fixed
but otherwise arbitrary s-sporse vector in R Then with probability at least - - for some positive constant B, is the unique minimizer to
min EER
||u/| subject y Bu,
provided that 2 loggn. The constant C3 = Co + 3) where Co some constant.
We note that the definition of based on re-scaling the vectors b1, b bn is done so that the columns of B are approximately unit-normed. The work in Kueng Gross (2014) extends the above result without assuming the isotropy property. Let = E[bb"],, where before b is drawn from distribution F on R" denote the covariance matrix. The anisotropic analysis in Kueng & Gross 2014) is based on two properties pertaining to the measurement matrix. The first is the incoherence property which is formally defined follows. The incoherence parameter is the smallest number ((F) such that
max IS
(b,,,)) S ((F) and max 15i5n
(b, [b, Sp()),
hold almost surely. The second property based on the conditioning of the covariance matrix. Specifically, it is based s-sparse condition number, for which we restate the definition from Kueng & Gross (2014)
Definition Kueng & Gross
2014)). The largest and smallest s-sparse eigenvalue of a matria X are given and Amin (8, X) = min [X
by Amaxx (s, X)
max Vv
[M]]2
Xv
The 8-sparse condition number of X is v:llv/loSa [M]l
Amax (s, (s
cond(s, s, X)
Amin (8, X)
Given these assumptions, the main result. in Kueng & Gross
2014) is stated below.
Theorem 2 (Kueng& Gross (0144).. Let B Vm Em b, be a measurement matria and let u be a fized
but otherwise arbitrary 8-sporse vector in TR. Define Kg max cond(ss E), cond( >-E> and let B > 1. If the number of measurements fulfills 2 CKa ((F) logn, n, then the solution of the convez program min ||um| subject to y= Bu, is unique and equal to u² with probability at least 1 -B
The proofs of Theorem I and Theorem are based on the dual certificate approach. The approach involves assuming the existence of dual certificate vector that satisfies certain conditions which ensures the uniqueness of the minimization problem. The remaining task is then to construct a dual certificate that satisfies these conditions. Since the conditions on the dual certificate will be used in our main analysis, we summarize the conditions on v in the following lemma.
Lemma 1 (Kunng & Gross 2014). Candes & Plan (011 ). Under the assumptions of and Theorem there ezists dual certificate vector v, in the row space of B, such that
vs sgu(u < and l|vs=lbo 1
(6)
In addition, it follows that
As/12 A A I|z, for any A E Ker(B).
(7)

---

Published in Transactions on Machine Learning Research (8/2024)
4 Theoretical Analysis
The dense and sparse coding problem studies the solutions of the linear system y Ax Bu. Given matrices A E Rx>p and B E R=*x and a vector y E R", the goal is to provide conditions under which there is a unique solution (x', u²), where u" is s-sparse, and an algorithm for recovering it. For ease of navigating the main results, Figure 1 shows the road-map of the main thcorctical results.
Theoretical analysis)
Techniral background
Feasibility analysis
Convex optimization
Theorem
Theorem
Lemma
Theorem 3
Theorem 4
Theorem 5
Theorem
Theorem
Figure 1: A road-map of the main theoretical results in the manuscript.
4.1 Feasibility problem
In this subsection, we first study the uniqueness of solutions to the linear system accounting for the different structures the measurement matrices A and B can have. A uniqueness result can be readily obtained by assuming orthogonality of Col(A) and Co)(B). In what follows, we establish uniqueness results for the general setting. The main result of this subsection is Theorem 4 which, under a natural geometric condition based on the minimum principal angle between the column space of A and the span of 8 columns in B, establishes a uniqueness result for the dense and sparse coding problem. Since the vector u in the proposed model is sparse, we consider the classical setting of an overcomplete mcasurement matrix B with >> m. The next thcorem provides uniqueness result. assuming certain direct sum representation of the space RT. We first note that, for A max with p >> m, any Ker(A A) can be added to any solution With that, consider uniqueness modulo the vectors in Ker(A), meaning any feasible solution is assumed to be in Ker(A)+
Theorem 3. Assume that there exists at least one solution to y Ax Bu, namely the pair (x*, u²). ux), Let S, with |S] s, denote the support of u², If Bg has full column rank and RT Col(A) @ Col(Bs), the only unique solution to the linear system, with the condition that any feasible s-sparse vector is supported on S and any feasible x is in Ker(A)+, is
Proof. Let (x, u), with u supported on S and x Ker(A)+ be another solution pair. follows that Aδ1 + (52)))s = 0 where 81 = x x" and 82 = u - u². Let U mxxr and V Rmxg be matrices whose columns the orthonormal bases of Col(A) and Col(Bs), respectively. The equation Aô1 + Bs can equivalently be written E (Ad1 U,),,
V.VV, = 0 with U, and V, denoting
the i-th columns of U and V, respectively. More compactly, we have [U v] { U
((Bs(())) V Ke
0.
Noting that the matrix [U v] has full column rank, the homogeneous problem admits the trivial solution implying that Ad, 0 and Bs = O. Since Bg has full column rank and ε1 E (Ker(A) n Ker (er(A))), it follows that 82 = 82 0. Therefore, u²) is the unique solution.
The uniqueness result in the above theorem hinges on the representation the space RT as the direct sum of the subspaces Col(A) and Co)(Bs). We use the definition of the minimal principal angle between two subspaces, and its formulation in terms of singular values (Björck & Golub 1973), to derive explicit geometric condition for the uniqueness analysis of the linear system in the general case.
Definition 2. Let U E moxr and V E mmxq be matrices whose columns are the orthonormal basis of Col(A) and (B), respectively. The minimum principal angle between the subspaces Col(A) and Col(B) is defined
7

---

Theorem 5. Assume that there exists at least one solution to y Ax + Bu, namely the pair (x", u²). Let S, with |S| = s, denote the support of u". Assume that Bg has full column rank. Let U e Rmrr and V R.xxy be matrices whose columns are the orthonormal bases of Col(A) and Col(Bs), respectively. Let Published in Transactions on Machine Learning Research (8/2024)
follows
T V
U, V)) =
max vECa
(8)
| 2 v
In addition,
where 01 denotes the largest singular value.
Theorem 4. Assume that there erists at least one solution to y - Ax + Bu, namely the poir (x", u²). Let S, with [S] = 8, denote the support of u². Assume that Bş has full column rank Let U RRaxr and Ve Rmxx be matrices whose columns are the orthonormal bases of Col(A) and Col(Bs), respectively. If Cos(p(U, V)) 01 V) < 1, the only unique solution to the lineor system, with the condition that any Seasible s-sporse vector u is supported on S and any feasible is in Ker(A)+, is (x", u²).
Proof. Consider any candidate solution pair (x* + 81, u² + 82) with d2 supported in S. We will prove uniqueness by showing that Aô1 + (s(52)s = 0 if and only if 81 = O and 82 = O. Using the orthonormal
U U²
basis sct U and V, Aő1 + (5( can be represented as Aδ1 + Bg(62)s = U v)
For
(²Bs(62)s)
simplicity of notation, let K denote the block matrix: K = U V.. If we can show that the columns of K
are lincarly independent, it follows that Ao + (5()))s = 0 if and only if Ao = and Bs(82)s = 0. We now consider the matrix K"K which has the following representation
Texr
Vexa
K"K-
V
1
gxr
rrx
[0 [0)xx
0 Orr
[ [0]
1xxq
+
UV gxx
With the singular value dccomposition of UTV being representation has the following equivalent form
UTV
QERT, the last matrix in the above Q
0
U
0
0
Σ
0
VTU
= 0
R
Σ
0
R
It now
0 VTU
U 0
0
Σ
follows that
is similer to the matrix
Hence, the nonzero eigenvalues of K are
Σ
0
1 o1, 1 S min(p, q), with o; denoting the i-th largest singular value of U'V. Using the assumptioo < 1 results the bound Amin KK > 0. It follows that the columns of K are linearly independent, and hence A6 = and (525))s = O. Since Bg is full column rank and 81 E (Ker(A) n Ker(A)-), it follows
that 8, = and 82- =
A restrictive assumption of the above theorem is that the support of the sought-after s-sparse solution u" is known. We can remove this assumption by considering Col(A) and Col(Br) where T is an arbitrary subset. of {1, 2, ...,,? n with = More precisely, state the following corollary whose proof is similar to the proof of Theorem 4
Corollary 1. Assume that there erists at least one solution to y Ax + Bu, namely the pair (x',u") u'). Let S, with |S| = 8, denole the support of u² and T be an arbilrary subset of {1,2 2..,....n. _. with (T] S 8. Assume that any 2s columns of B are linearly independent. Let U E gm<p and V E gmxx be matrices whose columns are the orthonormal bases of Col(A) and Col(B respectively. If (UU V) oi (UTV) 1, holds for all choices T,, the only unique solution to the linear system is (x',u") u') with the condition that any feasible is s-sporse and any feasible x is in --
Of interest is the identification of simple conditions such that (U(UV) < 1. The following theorem proposes one such condition to establish uniqueness.
max |uT v, = p. If s - the only unáque solution to the linear system, with the condition that any b
feasible s-sparse vector is supported on S and any feasible is in Ker(A (A) ) is ,²).
8

---

Published in Transactions on Machine Learning Research (8/2024)
Proof. It suffices to show that 01 1. Noting that 01 1 we use the following matrix norm inequality ||U*V S villu"V/l as follows: 0r S V= S vrps <1 1.
The constant j is the coherence of the matrix U (Donoho et al. 2005 Tropp 2004).
The above result
states that the mul coherence of U small, we can accommodate increased sparsity of the underlying signal component u². We note that, up to a scaling factor, 01 a (U'V) V) is the block coherence of U and V (Eldar et al. 2010). However, unlike the condition in Eldar al. (2010), we do not restrict the dictionaries A and B to have linearly independent columns. In the next subsection, we propose and analyze convex program to recover the dense and sparse vectors.
4.2 Dense and sparse recovery via convex optimization
We propose the following convex optimization program for the dense and sparse coding problem
min KER"
||Gx|| + +|ul|1 subject to y y Ax Bu.
(9)
Proof strategy: The Tikhonov matrix G is assumed to have full column rank. Our goal is to establish that, under certain conditions, the above minimization problem admits a unique solution (x", u²). The proof strategy as follows: First, we make the change of variables z = Gx, which allows us to rewrite the linear constraint as y = Hx + Bu, where H AGI, The second step is to eliminate the dense component in the constraint by applying the projection operator PCol(H)). This yields PCotE)) (y) P (Bu). Denoting = -= (B), we obtain Pool()) (y) = Cu. Focusing on the optimization problem with respect to u, we have a sparse recovery problem with the measurement matrix Č. To guarantee exact recovery for this problem, certain conditions on the matrix C are required. For instance, the results discussed in Section 3.2 require the rows of C to be sampled i.i.d. from some distribution F. However, if A and B are realized as random ii.d. matrices, the projection operator does not necessarily preserve the i.id. property, meaning Č may not meet the conditions for exact recovery. Therefore, a crucial part of our analysis the careful construction of the measurement matrices and to ensure that the resulting sparse recovery problem has measurement matrix with the desired structure for unique recovery, detailed below.
Construction of measurement matrices: First, note that Col(A)+ is an r-dimensional subspace of Ih"", where r = dim Col( AA Given A E Rmxp, either generated from deterministic or random model, we first form the matrix H = AG". We then sample r i.i.d. random vectors Cı, c from some distribution F on RP, meaning each sampled vector is a random vector of size RP. Let C = V Ei= e,c, be the scaled measurement matrix. Before we proceed construct the matrix C we make the following observations. Let the size of G be q x p. Since G has full column rank, the rank of G is p. It then follows that the rank of Gt is also p. Considering the matrix H AGt, since Gf has full row rank, the rank of H E m= is the rank of A. Hence, dim Col(H) random vectors, scaled by 7 and the remaining m r rows are such that each column of Ć lies in Col(H)+
r. We form matrix Č of size m p where its rows the sampled
Note this can always be achieved since Col(H)+ is an r-dimensional space in R Therefore, any point in Col(H)+ can be realized by picking the first r points at random and determining the rest of the entries from the constraints that define -ol It important to note that the rows of Õ are not i.i.d. (except the first r rows generated from the random model). The matrix C will be essential to our main analysis, as its rows sampled from the distribution F. We now form the matrix B E mxxx by constructing each of its columns as follows: b, è; + h, where b; is the i-th column of B, è is the i-th column of C, and h, is arbitrary vector that is in the column space of H. This ensures that Č = PCol(A) as desired. Figure summarizes the construction of the measurement matrices.
Thcorem 6. Let F a distribution of random vectors on R and C12 C2..... c, be r vectors sampled from F. The constants ((FF) and K, denole the coherence and sparse condition number associaled to F. Let z' == Gix* E T, where T = Ker(Pcol(B)- and dim Col(A') !. If 2 CR. ((F) B² slog n, (x", u²) the unique minimizer to with probability at least -8.
and u² be an s-sparse vector. Set y Ax* BBu.. Let 3 >
9

---

Published in Transactions on Machine Learning Research (8/2024)
Given R and G R construct = AGI,
2. Sample ii.d. random vectors c1, C2..... C, from F on R
3. Construct C = + Ei= e.c.
Č
vF
vF
C2
1
vFC,
Complete each column of C such that it lies in C
Construct each column of B: b, = č; + h; where h, e Col(H).
Figure 2: Flow chart that shows the construction of the measurement matrices.
Proof. We make a change variable z = Gx and rewrite the optimization in 9 as follows
min
|2| ||ull zuu
subject to y AG + Bu Hz Bu.
(10)
We structure the proof into 3 parts.
1. Optimality in the mixed objective
We consider generic feasible solution pair (z' + 6, u² + +8). Let the function f(z, u) define the objective in the optimization program. The idea of the proof is to show that any feasible solution is not minimial in the objective value, f(z" + 81, u2 + 52) 2 f(z", u²), with the incquality holding for all choices of 5 and 82 and equality obtained if and only ô, = 82 = O. Before we proceed, two remarks are in order. First, using the duality of the norm and the fo norm, there exists A with supp(A) с S", ||A such that (A, (62)s=) = [1(62)s= Second, the subgradient of the l norm u" is characterized follows: g supp(g)
and
11gs=lll I 1). It follows that sgn(u") A is subgradient of the & norm at u". It Ihen follows that the inequality ||u|| 2 ||u*|| + (sgn(ug) A, u u²) holds for any We lower bound f(z" + 81, u² + 82) as follows.
0||u1||1 (sgn(u
1z + 8111 ||u" 82111 2 2||z" 1 + 11111 2(z" 81) + ||u (sgn(ug) + +,,02) =f(z", u²) + 1| + (sgn(u + A A,62).
(11)
Above, the second equality uses the fact that z" E T and d, T The latter fact follows from the feasibility condition that H6, + Bo, and the application of the projection operator PCa(()) both sides.
2. Introducing the dual certificate
We next use the feasibility condition that H61 + B5, = 0 and introduce the dual certificate v. To climinate the component HỐ,, we project it onto the hrthogl complement of the range of H and obtain C62 = o where Č (C) We note that the previous relation follows from the construction the measurement matrices. We further consider reduced system by considering Cd2 = Recall that C is a matrix where each is sampled i..d. from the distribution F. With that, we essentially have sparse recovery problem with the measurement matrix C. Using Lemma. 1, and the assumptions of the theorem, there exists dual
10

---

Published in Transactions on Machine Learning Research (8/2024)
certificate Col(CT). With this, we continue with lower bounding f(z" + =1,1,, +62) ||2" + 51l12 + I|u + 62111 21|2*112 + || 12 + ||u^|/ + (sgn(ug) + A v,
u*
=f(x", u ) + (sgn(u3) - A v 02)).
(12)
It remains to show that (sgn(u3) + A v 52) > 0. By considering projections onto S and S and using the fact that (A (o)) [1(82)sc I1, we obtain
(sgn(u + + - v, 52) (sgn(ug) - Vs. (82)s) - (vs. (62) (62)
Σ || (ign((s)) - vs v=ll21((82) - ||v 00 (62)s=11 + (1(62)s=lli
(1(62)s 11(62) 8=22)s=111
(13)
1
4 11(82)s112 (1(82)
(1(6))s--11
(14)
4
The inequality in [3 the last inequality follow from the conditions on v from Lemma 1. Combining and the above bound with the final result noted in 14]. we have
12
f(z' + +01,u' u + +22 2 f(z" u²) + 18112 + - 11(22)s==11
(15)
3. Uniqueness of solution
We note that f'z + 81, u² + 82) f(z, u) if and only if [1(62)s==11 = 0 and d1 0. Since |1(82) S 211(62)s==le ll, the equality [1(62)s=111= = 0 implies that |1(82)s
(o)ss la O. With this, f(x 81, u + 52) = f(x, u)
if and only if 62 = O. Therefore, the solution (2", u²) achieves the minimal value in the objective, and is
a unique solution to [0)]. Finally, using the relation x* Giz guarantees unique solution to This concludes the proof.
Remark 1. Consider the following optimization program
min |Gx12 A|lul|,
subject to y= Ax + Bu,
(16)
where À > 0 is constant that balances the two terms in the objective. Following the same steps in the proof of Theorem 0 also guarantees unique solutions for the modified objective.
4.3 Special cases of analysis and discussion
We note few special cases of our main theorem in Theorem G First, when the Tikhonov matrix G is the identity matrix, the regularization on x is the standard l (minimum norm least squares) regularization. The main result continues to hold, with additional assumptions, when G = A. In this case, the optimization problem
min xEKer(A)-
||Ax| ||ul|2 subject to y Ax+
(17)
We note that the uniqueness result for the above problem is modulo restriction to the subspace Ker(A)+ We now state the following result.
Theorem 7. Let F a distvibution of random vectors on RpP and C12 C2,..., cr be vectors sampled from
F. The constants p(F) and K, denote the coherence and sparse condition number associated to F. Set y Axt + Bu" Let and dim (A) Assume the two conditions
B S
max 1
(BJ.A)
(18)
32
32 x 11
r 2 Cwa (FF (P)P8 B2 log (x", ,²) is the unique minimizer to
17 with probability at least 1 eB
11

---

Published in Transactions on Machine Learning Research (8/2024)
Proof. The proof follows the proof of Theorem 6 The main difference is that need to show that (sgn(ug) + A - 2B Ax" .2)) > O. By considering projections onto S and Se and using the fact that (A, (82)s=) = |((2)ss |11, we obtain
(sgn(ug)) + v- 2B"Ax" ;
(sgn(u Vs (82)s) (vsr, (02)s.) + (1(62) s-11s (2["" Ax"Is (
(2 Ax") |S~ (62)s²)
2 (gg)( Vs ( v 00 (62)
(1(6)) 1-112
2 B A x 112 |1(6))s122 - 2 max
(B A)
) x 100 (62))(0)
[.
1
2 4
[1(82)s l2
(102)s 0 + +1(62) ||1
|162)slll
(62)s |11
4
16
16
5
11
(1(62)sl12 +
((8))ss1
= 16
16
10
11
//2 [1(62)s=111
1
(1(22)
(2)())))
|||
16
16
The rest of the proof is similar to the proof of Theorem 6
4.4
Comparison to compressive sensing
We note that the dense and sparse coding problem problem equivalently be formulated y Ax+ Bu
A
B
X
Applying standard compressive sensing (CS) results imposes uniform conditions on [A BJ, which
u
may lead to sub-optimal recovery guarantees. We will use Theorem to illustrate the difference between the CS approach and ours. For concrcte example, let A be 20 x 20 invertible matrix, B be 20 x 80 matrix and
xx
set k = 2. To recover
exactly, one condition based on CS (see Theorem 1.7 in Davenport et al. (2012)) is:
(1 (1+ [A
(1 1+
< <
+ <
14AA
P.
where A|A B] denotes the mutual coherence of the combined dictionary. Note that the range of p[A B is [mo. 1] where No denotes the Welch bound (see Definition 1.5 in Davenport et al. (2012)). We make the following observations:
The maximum sparsity decreases p increases. With p 20, mutual coherence of the combined dictionary needs to be at most 1 /43 x 0.0233.
In our approach, to allow for sparsity k = 2, the block coherence needs to be al most 1/(2v200 R 0.1118.
Theorem relies block coherence and does not require coherence within the blocks A and B. This provides flexible model, allowing A to be deterministic coherent dictionary, for example.
Next, consider applying & minimization and standard compressive sensing theory guarantee uniqueness given the measurement matrix R [A B). One guarantee based incoherence (sce Theorem 1.1 in Candes & Plan 20111 states that the number of measurements must be on the order of pp + k) log(p + n), where is the coherence of the combined dictionary R. In contrast to the mutual coherence mentioned earlier, μ4 is the smallest number such that the following equality holds for any row of R denoted by a:
(a(i)1 < P4r
max 15t5(p+x)
where a(i) denotes the i-th entry of a. It is typically assumed that there is an underlying distribution F from which the rows R = AA B] are sampled independently and identically. We note that the range μe, for the measurement setup Candes & Plan (2011), [1, + p). The implication of this is that the sample complexity implicitly requires μ. = O(1) In the case of mixed dictionaries, as our setup, coherent matrix A can lead to sub-optimal number of measurements.
12

---

Published in Transactions on Machine Learning Research (8/2024)
5
Experiments
The codes for reproducing the experiments in this section can be found on GitHub: https: http::///ithub..o. com/ banosth/densase and
5.1 Phase transition curves
We generate phase transition curves and present how the success rate of the recovery, using the proposed model, changes under different scenarios. To generate the data, we sample random matrices A E Rmxp and B E Imxx whose columns have expected unit norm and fix the number of columns of B to be n = 100. The vector u E R has randomly chosen indices, whose entrics are drawn according a standard normal distribution, and ensures that does not belong in the null space of A, and hence degenerate cases avoided. We normalize both and u to have unit norm, and generate the measurement vector y E R y Ax Bu.
IRP is generated
A² where y IRm random vector. The construction
To generate the transition curves we vary the sampling ratio a = m E [0.05, 0.95] and the sparsily ralio ntp in the same range. Note that the sensing matrix in our model is [A B]; therefore, our definition of takes into account both the size of A and B. In the case where we revert to the compressive sensing scenario (p = 0), the sampling ratios coincide. We solve the convex optimization problem of (17) to obtain the numerical solution pair (x, û) using CVXPY (Diamond & Boyd 2016 Agrawal ct al., 2018). and register a
successful recovery if both | < and - Se, 6, with = 10-3 For each choice of and p, we average |
100 independent runs estimate the success rale.
Figure 3 shows the phase transition curves, indicating the probability of successful recovery, for p E 10.1m, 0.5m} to highlight different ratios between p and We observe that incrcasing leads to a deterioration in performance. This is expected, as this creates a greater overlap on the spaces spanned by A and B. We can view our formulation as modeling the noise of the system. In such a case, the number of columns of A encodes the complexity of the noise system: as p increases, so does the span of the noise space. Extending the signal processing interpretation, note that we model the noise signal x as dense vector, which be encoding smooth areas of the signal that correspond to low-frequency components. On the contrary, the signal has, by construction, sparse structure, containing high- free-frreeency information, interpretation that will be further validated on real data in Section 5.4
= 0.1m
p = 0.5m
1177 0.95
1.0
0.95
1.0
0.8
0.77
0.8
0.59
0.6
=/
0.6
0.41
0.4
0.41
0.4
0.05 0.23
0.2
0.23
0.2
0.0
0.05
0.0
0.42
0.74
0.74
m
m
Figure Phase transition curves for p 0.1m (left) and p 0.5m (right). Colors represent the probability of successful recovery, ranging from black (vector recovery failed in all trials) to yellow (recovery was always successful).
5.2 Noisy compressive sensing
If can be interpreted as noise vector, how does our model compare to noisy compressive sensing? Compressive sensing be extended to the noisy case, which allows for the successful recovery of sparse
13

---

Published in Transactions on Machine Learning Research (8/2024)
signals under the presence of noise, assuming upper bound on the noise level. In the rest of the section we examine how the proposed model, which incorporates both spanse and dense components, fares against this noisy variant.
0 = O. 0.1m
0.5.p = 0.5.p 0.1m
0.95, p 0.5, 0.1m
Namallzed casur 1eus7la
1.000
Chre
Oure
1.00
Our
0.75
CS
0.8
0.75
CS
0.0
Nunudieall
0.50
SNR (dD)
SNR (dB)
SNR (ID)
(a)
(b)
(c)
0.5.p 0.05.p 0.5m
0.5. 0.5. 0.5m
0.95, 0.5, 0.5m
Chrra
1.00
Ouns
Our
Norasized ertrr
0.76
0.75
0.50
0.50
Nurnalied
0.50
0.25
0.25
0.25
0.00
-00
-20
40
-10
-20
20
40
-10
-20
70
SNIt (4D)
SNR (dD)
SNR (BB)
(d)
(e)
(f)
Figure 4: Normalized recovery error of u as the SNR varies (lower is better).
We, again, fix the number of columns in B to be n 100, and generate the matrices A E Rmxp and B E Rmxn, well as the vectors x² Rp and u² R", before. We define the signal-to-noise ratio as SNR = 20 1og
||u*||, and iterate over the range [040 40dB). To vary the SNR, we normalize both
vectors and scale u' by 10 exn For our proposed method, we solve the optimization of (9 whereas for noisy compressive sensing we solve
û arg min ||u|||
subject to lyy - Bull2 < ||Ax 1l2
(19)
and report the normalized error l lla for the two methods averaging 100 independent runs.
| lla
We present the SNR curves in Figure 4 As an initial observation, note that noisy compressive sensing, in every case, recovers a vector when the energy of the noise is less than that of the signal (for a SNR> OdB), and in most scenarios full recovery is not achieved unless the ratio is very large (SNR> 25dB). That is expected, since the results for those settings assume an upper bound on the noise level. In contrast, our proposed model is able to recover both signals even when the norm of x is 100 times larger than that of u, at the cost of having access to the additional measurement matrix A.
For low sparsity ratios (Figures a and (d)), we are able to recover both signals in every experiment using our model, whereas compressive sensing exhibits the behaviour we discussed above. Increasing the sparsity ratio while keeping the number of samples the same (Figures 4b) and (e)) results a significant reduction performance for both models (note the different axis scaling for these figures). This in line with both the results for noisy compressive sensing and our results presented in Section 4 (as well as the phase transition curves of the previous subsection). When the overlap between A and B is greater (Figure [e)) our model suffers a greater performance hit, as is expected from our analysis; note that noisy compressive sensing is unaffected by the relative size of A and B, since it only makes assumptions about the noise level and not its span. Finally, we observe that increasing the number of measurements (Figures 4 c) and (f)) restores performance, line with our analysis.
Remark: Note that the large sparsity ratios (p 0.5, corresponding Figures 4 [bb. (c), (c), and (f)) violate assumptions in Section and recovery is not. expected based on the transition curves of the previous
14

---

Published in Transactions on Machine Learning Research (8/2024)
subsection. However, we include them for illustration, as for smaller values of p our model always recovered both vectors. As key takeaway from this line of experimentation, we recommend the use of our model in every case where there is a structured interference with significant norm. In cases where the norm of the signal of interest is dominating (SNR= 40dB) and there is some form of degeneracy (there a large overlap between the signal spaces and u barely sparse), noisy compressive sensing may be more appropriate.
5.3 Sensing with real data
In this section, we present experiments real data using random sensing matrices. The real data we consider is the MNIST database of handwritten digits (LeCun 1998 LeCun et al., 1998). Through these experiments, we want to (i) showcase the performance of our model on actual, real data and (ii) show the efficacy of our algorithm when using overcomplete sensing matrices. To generate overcomplete dictionaries, we proceeded
Bu
u
y
Ax
X
Figure 5: Decomposition of an MNIST image to its sparse and dense components. We visualize the minimization of the terms in (20 the input. y is adequately reconstructed (left), the component Ax is smooth relative to Bu (middle), and is sparse.
follows: as MNIST images can be scen as vectors y 784, we first generated a random orthogonal matrix in 784x784 We used half of the columns of that matrix as base for A E 781x1021 and the other half for generated linear combinations of each base. To avoid artificial
B 784x10024 the rest of the columns orderings that might result when using certain optimizers, conclude the matrix generation with random column permutations. These matrices, while in combination they do span 784,, were not the generating model for the MNIST dataset. As such, we slightly alter the optimization problem of gg] to relax the exact. reconstruction, yielding:
min ||A + Bu y1l + +|| ? + |ull1- x,u
(20)
In our experiments, we use = 3 and X 0.01. A visual decomposition of such an image is presented in Figure 5
Both u and x have their expected properties: u is visibly sparse, with few nonzero elements and x has a fairly dense structure. Moreover, we observe that the component of Ar seems slightly more fainted compared that of Bu.
To further validate this observation computed both the Euclidean norm and total variation for each component, proxy for smoothness, and plotted the distributions of total variation in Figure D The distributions were computed using 10000 training samples. The distribution of the Euclidean norm was very similar and can be found in the Appendix, Figure 13 Observing the distributions of Ax and Bu we note that the distribution corresponding to the sparse component is skewed to higher values of total variation. This empirically validates the effectiveness of the smoothness regularization of (9) even when sensing using random matrices. As final remark, we attempted use in sparse coding framework to recover a sparse vector. However, in every instance the solver failed to converge and produce sparse vector; this is, to
15

---

Published in Transactions on Machine Learning Research (8/2024)
331
0312
335
033
3.0 340
54
Tra Vatasonn
Figure Total variation distribution for the components Ar and Bu of MNIST images. We quantify the qualitative difference in smoothness between Ax and Bu in 20 supporting the qualitative difference of Figure
extent, expected B generated using only half the columns of an orthogonal matrix and therefore is unable to fully span the image space, failing to adequately represent all the images in the data set.
The main analysis in this paper is based on the measurement matrices and the Tikhonov matrix satisfying certain conditions, such as randomness in the matrix B. However, in practice, efficient matrices are not always available, and random matrices might not be optimal for every data set. Dictionary learning refers to
the problem of learning A and B from data (Agarwal al. 2014 Chatterji & Bartlett 2017 Garcia-Cardonal
& Wohlberg 2018). Based on unrolled neural architectures for the sparse coding model (B 0) (Tolooshams
et al. 2020 Gregor & Lecun 2010), the next section proposes unrolled autoencoder to infer dense and sparse representations and learn dictionaries from data.
5.4
Dictionary learning based neural architecture for dense and sparse coding
We mitigate the drawbacks of convolutional sparse coding model in capturing wide range of features from natural images by proposing dense and sparse dictionary learning; the framework learns a diverse set of features (smooth features via and high-frequency features appearing sparsely through B). We formulate the dense and sparse dictionary learning problem as minimizing the objective
min } | I AX BU A.B.X.U
1 |AX + UuIl 2X,
+
(21)
which can solved using the following alternating minimization steps
1
U arg min X,U
Y ( UI +
|A + Uul
(22)
2
A (1+1) ((+1) = arg min
Y - A - B.
(23)
A.B
2
where Y R X R and U e Rax! with I is the total number of data examples. By design choice, we optimize only the reconstruction loss when updating the dictionarics. Basod on the above alternating updates, we use deep unrolling to construct an unrolled neural network (Tolooshams al. 2020 Gregor & Lecun 2010), which we term the dense and sparse autoencoder (DenSaE), tailored to learning the dictionaries from the dense and sparse model. The encoder maps Y into dense matrix Xx and sparse one UT using two sets of filters of A and B through a recurrent network. A encodes the smooth part of the data (low frequencies). and B encodes the details of the signal (high frequencies). The encoding is achieved by unrolling T proximal gradient iterations shown below
X, = X,-1 02 AT(Y-(112
10V-((1)) 1 AX. -BU,-)) X
(24)
U, = Sy (U, + a
B.
BT -XX,11111 -B,,1)),
16

---

Published in Transactions on Machine Learning Research (8/2024)
where az and Qu step sizes, and Sb; with b auduu is the activation function; for non-negative sparse coding, the activation is ReI.Ux(=) (z b) 1226, and for general sparse coding, it is Shrinkage, ReLU,(z) ReLUx(-z) (Tooooshamm et al. 2020).
Having a non-informative prior on Ax in DenSaE implies that X2 - co. The parameters azz, Ous Xu are tuned empirically. The decoder reconstructs the image using the generative model y = Axr Bur. For classification, we use uy and X7 as inputs to linear classifier C' that maps them to the predicted class q. The dictionaries A and B are learned via. backpropagation. We remark that b = a,, A larger value of b in the proximal mapping Sy enforces higher sparsity u, and smaller value of X promotes smoothness Ax. We learn the dictionaries A and B, along with the classifier C, by minimizing the weighted reconstruction (Rec.) and classification (Logistic) loss, represented as (1 (1-8) 3) Rec. + 3 Logistic), where 3 E [o, 1]. We note that, as 3 increases, the network shifts from reconstructing objective into a more predictive one. Figure shows the DenSaE architecture. We examined the following questions
Encoder
Decoder
Repeat T times
Og T
X
xy
y
y
a₂ B
Sh
ur
B
B
S
A
Classifier
Figure 7: DenSaE. The vector comprises the normalized features stacked plus scalar for the classifier bias, Sz and Smax are the soft-thresholding and soft-max operators, respectively.
(i) How do the discriminative, reconstruction, and denoising capabilities change as we vary the number of filters in A vs. B?
(ii) What is the performance of DenSaF compared to sparse coding networks?
(iii) What data characteristics does the model capture?
As baselines, we trained two variants, CSCNethyp and CSCNetLs, of CSCNet (Simo & Elad 2019). an architecture tailored to dictionary learning for the sparse coding problem y = Bu. Since all three networks are convolutional, A and are Toeplitz matrices that perform the sum of convolutions using multiple filters. In CSCNethyp- the bias is tuned a shared each filter by minimizing the reconstruction loss. When the dictionaries are non-convolutional, we call the network SCNet.
In CSCNetr.s. we learn different bias for
5.4.1 DenSaE strikes balance between discriminative capability and reconstruction
We study the case when DenSaF is trained on the MNIST dataset for joint reconstruction and classification. We show (i) how the explicit imposition of sparse and dense representations DenSaE helps balance discriminative and representation power, and (ii) that DenSaE outperforms SCNet. We warm start the training of the classifier using dictionaries obtained by first training the autoencoder with 0.
Characteristies of the representations Xy and uy: To evaluate the discriminative power of the representations learned by only training the autoencoder, we first trained the classifier given the representations. Specifically, we first trained A and B with 3 = O, then trained with 3 1. We call this disjoint training. Table 1 shows the classification accuracy (Acc.), l reconstruction loss (Roc.), and the relative contributions, expressed as percentage, of the dense or sparse representations to classification and reconstruction for disjoint training. Fach column of [A, B), and of C, corresponds to either dense sparse feature. For
17

---

Published in Transactions on Machine Learning Research (8/2024)
Table 1:
DenSaE's performance on MNIST dataset from disjoint training.
A+B is defined as
# columns + # columns of B 100.
columns of A
SCNetts
SCNelayp
200A 200B
395B
375B
A
1.25%
6.25%
50%
B+B
Acc.
94.16 % 98.32%
98.18%
98.18%
96.98%
Rec.
1.95
6.80
6.83
6.30
3.04
contribution to important class features
0%
0%
0%
A contribution to important features
8%
28%
58%
reconstruction, we find the indices of the 50 most important columns and report the proportion of these that represent dense features. For each of the 10 classes (rows of C), we find the indices of the 5 most important columns (features) and compute the proportion of the total of 50 indices that represent dense features. The first row of Table | shows the proportion of rows of [A B that represent dense features. Comparing this row, respectively the third and fourth row reveals the importance of for reconstruccion, and of for classification. Indeed, the Acc. and Rec. of Table [ show that, as the proportion of dense features increases, DenSaE gains reconstruction capability but results in a lower classification accuracy. Moreover, in DenSaE, the most important features in classification are all from B, and the contribution of A in reconstruction is greater than its percentage in the model, which clearly demonstrates that dense and sparse coding autoencoders balance discriminative and representation power.
Both Tables 1 and show that DenSaE outperforms SCNetts in classification and SCNetayp in reconstruction. Specifically, for joint training, Table 2 (columns 2,3 and row J1) shows that. DenSaF outperforms SCNethyp for reconstruction (32.61 < 47.70) while it is competitive for classification (98.61 > 98.59). Moreover, Table 2 (cols 1, 3 and Jo.75 and J1) highlights that DenSAE has significantly better classification (98.61 > 96.06) and reconstruction (32.61 < 71.20) performances than SCNel1s- Moreover, we observed that in the absence of noise, training SCNetLs results dense features with small negative biases, hence, making its performance close to DenSaE with a large number of atoms A. We see that SCNetr, the absence of a supervised classification loss fails to learn discriminative features useful for classification. On the other hand, enforcing sparsity in SCNethyp suggests that sparse representations useful for classification.
Table 2: DenSaE's performance on MNIST dataset from
How do reconstruction and classifi- cation capabilities change as we vary 3 in joint training?: In joint training of the autoencoder and the classifier, it. is natural to expect that the reconstruc- tion loss should increase compared to dis- joint training. This is indeed the case for SCNetts; as we go from disjoint to joint training and as 3 increases (TTable (2), the reconstruction loss increases and classifi- cation accuracy has an overall increase. However, for 8 1, joint training of both networks that enforce some sparsity on their representations, SCNethyp and Den- SaF, improves reconstruction and classification.
joint (Jg) training.
SCNet1s
SCNettsp
396B
5A
376B
25A
200A
200B
1.25%
6.25%
50%
A+B
Acc.
96.61%
97.97%
97.07%
97.68%
96.46%
Jo.5
Rec.
2.01
0.87
0.58
0.58
0.34
Acc.
96.91%
08%
98. 08.19%
23%
97.64%
Jo.75
Rec.
2.17
1.24
0.75
1.11
0.51
Acc.
97.23%
98.51%
98. 08.23%
98.44%
97.81%
Jo.95
Rec.
4.48
1.03
1.22
1.32
0.67
Acc. 96.06%
98.59%
98.61%
98.56%
98.40%
J1
Rec.
71.20
47.70
32.61
30.20
25.57
For purely discriminative training (3 = 1), DenSaE outperforms both SCNelrs and SCNethyp in classification accuracy and representation capability. We speculate that this likely results from the fact that, by construction, the encoder from DenSaE socks produce two sets of representations: namely a dense one, mostly important for reconstruction and a sparse one, useful for classification. In some sense, the dense component acts as a prior that promotes good reconstruction.
18

---

Published in Transactions on Machine Learning Research (8/2024)
Noisy
Ax
Bu
Denoised
B
a) DenSaE 4A 60B
Original
Implicit Ax Implicit Bu
Denoised
Implicit
Implicit B
b) CSCNetLs
Unused
Figure Visualization of a test image for T = 50. a) DenSaE (4A, 60B), b) CSCNetLs. Bu images are scaled and plotted with a different colormap for visualization purposes.
5.4.2 Denoising
We trained DenSaE for supervised image denoising when using BSD432 and tested it on BSD68 (Martin
et al. 2001). All the networks trained for 250 epochs using the ADAM optimizer (Kingma 2014 and the filters are initialized using the random Gaussian distribution. The initial learning rate is sct to 10- and then decayed by 0.8 every 50 epochs. We set of the optimizer to be 10-3 for stability. At every iteration, a random patch of size 128 x 128 is cropped from the training image and zero-mean Gaussian noise added it with the corresponding noise level. We varied the ratio of number of filters A and B the overall number of filters was kept constant. We evaluate the model the presence of Gaussian noise with standard deviation of (15, 25, 50, 75).
Ratio of number of filters in A and B: Unlike recon- struction, Table shows that the smaller the number of filters associated with A, the better DenSaF can denoise images. We hypothesize that this is a consequence of our findings from Section 4 that the column spaces of A and B are suitably unaligned, the easier is the recovery and u.
Table 3: DenSaE's denoising performance on BSD68 as the ratio of filters changes.
1A63B
4A60B 8A56B
16A48B
32A32B
15
30.21
30.18
30.18
30.14
29.89
25
27.70
27.70
27.65
27.56
27.26
Dense and sparse vs. sparse coding: Table A shows that DenSaE (best network from Table 3) denoises images better than CSCNethyps suggesting that the dense and sparse coding model represents images better than sparse coding.
50
24.81
24.81
24.43
24.44
23.68
75
23.31
23.33
23.09
22.09
20.09
Dictionary characteristics: Figure 8 (a) shows the decom- position of noisy test image (7= 50) by DenSaE. The figure demonstrates that Ax captures low frequueyy content while Bu captures high-frequency details (edges). This is corroborated by the smoothness of the filters associated with A, and the Gabor-like nature of those associated with (Mehrotra et al. 1992.. We observed similar performance when we tuned Ag and found that, as X₂ decreasos, Ax captures lower frequencics, and Bu broader range.
Table 4: DenSaE vs. CSCNet on BSD68, reporting mean (std).
DenSaF
CSCNethyp
CSCNetr.
15
30.21 (1.74) 30.12 (1.70) 30.34 (1.79)
25
27.70 (1.89) 27.51 (1.81) 27.75 (1.89)
50
24.81 (1.98) 24.54 (1.85) 24.81 (1.97)
75|
23.33 (1.96) 22.83 (1.73) 23.32 (1.95)
CSCNet deviates from sparse coding and implicitly lcarns Ax + Bu model in the presence of noise: By training the biases, CSCNet1s deviates from the sparse coding model; the neural net work's bias directly related to the sparsity enforcing The larger this bias, the sparser the representations. We observed that CSCNetLs automatically segments filters into three groups: one with small bias, one with intermediate ones, and a third with large valies (sce Figure 12). We found that the feature maps associated with the large bias values are all zero. Moreover, the majority of features associated with intermediate bias values, and are sparse, in contrast to the small
An.
19

---

Published in Transactions on Machine Learning Research (8/2024)
number of feature maps with small bias values, which are dense. We call the dictionary atoms, corresponding such small biases, implicit A. Similarly, dictionary atoms with moderate biases can be seen as implicit B.
These observations suggest that autoencoders implementing the sparse coding model (y = Bu), when learning the biases by minimizing reconstruction error, implicitly perform two functions. First, they select the optimal number of filters. Second, they partition the filters into two groups: one that yields dense representation of the input, and another that yields a sparse one. In other words, the architectures trained in this manner implicitly learn the dense and sparse coding model. Figure ( shows the filters.
The above-mentioned interpretation of CSCNet with learned biases offers to revisit the optimization-based model used to construct the autoencoder; if the network implicitly learns a bipartite representation, why not explicitly model that structure? Through our experiments, we showed that doing so leads to increased performance with the recovered dictionaries and representations not deviating from their expected behavior. The resulting network is also more interpretable, as we can directly visualize and analyze cach component.
6 Conclusions
This paper proposed a novel dense and sparse coding model for a flexible representation of signal y = Ax + Bu. Our first result gives verifiable condition that guarantees uniqueness of the model. Our second result uses tools from anisotropic compressed sensing to show that, with sufficiently many linear measurements, a convex program with & and & regularizations can recover the components x and uniquely with high probability. Numerical experiments on synthetic and real data confirm our observations.
We proposed a dense and sparse autoencoder, DenSaE, tailored to dictionary learning for the Ax + Bu model. DenSaE, naturally decomposing signals into low- and high-froquency components, provides a balance between learning dense represenlations that are useful for reconstruction and discriminative sparse represenlations. We showed the superiority of DenSaE to sparse autoencoders for data reconstruction and its competitive performance in classification.
Acknowledgments
Abiy Tasissa acknowledges partial support from the National Science Foundation through grant DMS-2208332 Demba Ba's and Emmanouil Thcodosis's work is supported by the National Science Foundation under Cooperative Agreement PHY-2019786 (The NSF AI Institute for Artificial Intelligence and Fundamental Interactions, attp://iaifi.org: All the authors would like to thank the the anonymous reviewers for their valuable foodback.
Author Contributions
Abiy Tasissa, Emmanouil Theodosis and Demba Ba studied the model in 11 and worked on the theoretical analysis presented in Section 4. Emmanouil Theodosis conducted all the experiments in Sections 5.1, 5.2 and 5.3. Bahareh Tolooshams designed and conducted the experiments in Section 5.4 for dictionary tearning-based neural architectures. All authors contributed to the writing of the manuscript.
References
Alekh Agarwal, Animashree Anandkumar, Prateek Jain, Praneeth Netrapalli, and Rashish Tandon. Learning sparsely used overcomplete dictionaries. In Maria Florina Balcan, Vitaly Feldman, and Csaba. Szepesvári (eds.), Proc the 27th Conference on Learning Theory, volume 35 of Proceedings of Machine Learning Research, pp. 123-137, Barcelona, Spain, 13-15 Jun 2014. PMLR.
Alckh Agarwal, Anima Anandkumar, Pratock Jain, Pranccth Netrapalli, and Rashish Tandon. Learning sparsely used overcomplete dictionaries via alternating minimization. SIAM Journal on Optimization, 26: 2795, 2016.
Akshay Agrawal, Robin Verschueren, Steven Diamond, and Stephen Boyd. A rewriting system for convex optimization problems. Journal of Control and Decision, 5(1):42 -00 2018.
20

---

Published in Transactions on Machine Learning Research (8/2024)
Michal Aharon, Michael Elad, and Alfred Bruckstein. k-svd: An algorithm for designing overcomplete dictionaries for sparse representation. TEEF Transactions on signal processing, 54(11 (4(11))4311 1:4111-2,, 2006.
Jean-François Aujol, Gilles Aubert, Laure Blanc-Féraud, and Antonin Chambolle. Image decomposition:
application to textured images and SAR images. Technical Report RR-4704, INRTA, January 2003. URL
https://hal.intt Sttriii.f/inria-0l000
Richard Baraniuk, Mark Davenport, Ronald DeVore, and Michael Wakin. A simple proof of the restricted isometry properby for random matrices. Constructive Approcimation, 28(3):253 263, 2008.
Amir Beck and Marc Teboulle. A fast iterative shrinkage-trresooddnng algorithm for linear inverse problems.
SIAM journal on imaging sciences, 2(1):183 202, 2009.
Marcelo Bertalmio, Luminita Vesc, Guillermo Sapiro, and Stanley Osher. Simultancous structure and texture image inpainting. IEEE transaclions on image processing, 12(8):882 889, 2003.
Åke Björck and Gene H Golub. Numerical methods for computing angles between linear subspaces. Mathe- malics of compulation, 27(123):579 594, 1973.
Jérôme Bobin, Jean-Luu Starck, Jalal M Fadili, Yassir Moudden, and David L Donoho. Morphological component analysis: An adaptive thresholding strategy- TEEE transactions on image processing, 16(11): 2675 2681, 2007.
Emmanuel Candes, Mark Rudelson, Terence Tao, and Roman Vershynin. Error correction via lincar programming. In 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS105), pp. 668 681. IEEE, 2005.
Emmanuel Candes. The restricted isometry property and its implications for compressed sensing. Comples rendus mathemalique, 346(9-10):55) 592, 2008.
Emmanuel J Candes and Yaniv Plan. A probabilistic and ripless theory of compressed sensing. IEEE transactions on information theory, 37(11):7235-725) 2011.
Emmanuel Candes and Terence Tao. Decoding by linear programming. IEEE transactions on information
theory, 51 (12):4203-422) 42155-22115, 2005.
Emmanuel J Candes and Terence Tao. Near-optimal signal recovery from random projections: Universal
encoding strategics? IEEE transactions on information theory, 52(12):5406-54255 2006.
Emmanuel Candès, Xiaodong Li, Yi Ma, and John Wright. Robust principal component analysis? Journal of the ACM (JACM), 58(3):1-37, 2011.
Chein-l Chang and Shao-Shan Chiang. Anomaly detection and classification for hyperspectral imagery, IEEE transactions on geoscience and remote sensing, 4016):1314-1325,, 2002.
Niladri S Chatterji and Peter L Bartlett. Alternating minimization for dictionary learning: Local convergence
guarantees. arXiv:1711.00 1..6631111.63..,. pp. 1-26, 2017.
Scott Shaobing Chen, David L Donoho, and Michael A Saunders. Atomic decomposition by basis pursuit. SIAM review, 1391) 2001.
Ingrid Daubechies. Ten lectures on wavelets. SIAM, 1992.
Mark A Davenport, Marco F Duarte, Yonina C Eldar, and Gitta Kutyniok. Introduction to compressed sensing., 2012.
Gcoff Davis, Stephane Mallat, and Marco Avellaneda. Adaptive greedy approximations. Constructive approcimation, 13(1):57 98, 1997.
Steven Diamond and Stephen Boyd. CVXPY: Python-embedded modeling language for convex optimization. Journal of Machine Learning Research, 17(8))11-5, 2016.
21

---

Published in Transactions on Machine Learning Research (8/2024)
David C Dobson and Fadil Santosa. Recovery of blocky images from noisy and blurred data. SIAM Journal on Applied Mathemalics, 56(4):1181-1198, 1996.
David L Donoho and Michael Elad. Optimally sparse representation in general (nonorthogonal) dictionaries via l minimization. Proc. the National Academy of Sciences, 100(5):2197-2202, 2003.
David L Donoho and Xiaoming Huo. Uncertainty principles and ideal atomic decompasition. IEEE transactions on information theory, 47(7):2845 2862, 2001.
David L Donoho and Philip B Stark. Uncertainty principles and signal recovery. SIAM Journal on Applied Malhemalics, 49(3):906 931, 1989.
David L Donoho, Michael Elad, and Vladimir N Temlyakov. Stable recovery of sparse overcomplete representat ions in the presence of noise. IEEE Trunsactions on information theory, 52(1):6-1) 18, 2005.
Michael Elad and Alfred M Bruckstein. generalized uncertainty principle and sparse representation in pairs of bases. IEFE Transactions Information Theory, (89)):2558-2555 2002.
Michael Elad, J-T. Starck, Philippe Querre, and David L. Donoho. Simultaneous cartoon and texture image inpainting using morphological component analysis (mca). Applied and computational harmonic analysis, 19(3):340 358, 2005.
Yonina C Eldar, Patrick Kuppinger, and Helmut Bolcskei. Block-sparse signals: Uncertainty relations and efficient recovery. IEEE Transactions on Signal Processing, 3804)23042-300 3054,, 2010.
Axel Flinth. Optimal choice of weights for sparse recovery with prior information. IEFE Transactions on Information Theory, 62(7):4276 4284, 2016.
Michael P Friedlander, Hassan Mansour, Rayan Saab, and Özgür Yilmaz. Recovering compressively sampled signals using partial support information. IEEE Transactions on Information Theory, 58(2):1122 1134, 2011.
Cristina Carcia-Cardont and Brendt Wohlberg. Convolutional dictionary learning: A comparative review and new algorithms. IEEE Transactions on Computational Imaging, 4(3):366 81, September 2018. doi: N0.1109/TCT.2018.28822
Karol Gregor and Yann Lecun. Learning fast approximations sparse coding. Proc. International Conference on Machine Learning (ICML), pp. 399-406, 2010.
Rémi Gribonval and Morten Nielsen. Sparse representations in unions of bases. IEEE transactions Information theory, 39(12))3320-333) 3325,, 2003.
Diederik P Kingma. Adam: A method for stochastic optimization. arXiv preprint orXiv:1412.6986 2014.
Richard Kueng and David Gross. Ripless compressed sensing from anisotropic measurements. Linear Algebra and its Applications, 441:110-125 2014.
Patrick Kuppinger, Giuseppe Durisi, and Helmut Boleskei. Uncertainty relations and sparse signal recovery for pairs of general signal sets. IEEE transactions on information theory, 58(1):263 277, 2011.
Yann LeCun. The mnist database of handwritten digits. http://yann. lecun. com/exdb/ /e/////////mis/////////// 1998.
Yann LeCun, Lóon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document. recognition. Proceedings of the IEEE, 86(11):2278 2324, 1998.
Lixiang Lian, An Liu, and Vincent KN Lau. Weighted lasso for sparse recovery with statistical prior support information. IEEE Transaclions on Signal Processing, 66(6): 1618, 2018.
Julien Mairal, Francis Bach, and Jean Ponce. Task-driven dictionary learning. IEEE transactions on pottern analysis and machine intelligence, 34(4):791 804, 2011.
22

---

Published in Transactions on Machine Learning Research (8/2024)
Stéphane Mallat. A wavelet tour of signal processing. Elsevier, 1999.
Stéphane Mallat and Guoshen Yu. Super-resolution with sparse mixing estimators. IEEE transactions image processing, 19(11):2889- 2900, 2010.
Hassan Mansour and Rayan Saab. Recovery analysis for weighted 11-minimization using the null space property. Applied and Computational Harmonic Analysis, 43(1):23-38, 2017.
Martin, C. Fowlkes, D. Tal, and J. Malik. A database of human segmented natural images and its application evaluating segmentation algorithms and measuring ecological statistics. In Proc. 8th Int Conf. Computer Vision, volume 2, pp. 416-423, July 2001.
R. Mchrotra, K.R Namuduri, and N Ranganathan. Gabor filter-based edge detection. Pattern Recognition, 25 (12):1479 94, 1992. ISSN 0031-3203.
Vishal Monga, Yuelong Li, and Yonina C Eldar. Algorithm unrolling: Interpretable, efficient deep learning for signal and image processing. IEEE Signal Processing Magazine, 38(2):18 44, 2021.
Nam H Nguyen and Trac Tran. Exact recovcrability from dense corrupted observations via 11-minimization. IEEE transactions on information theory, 59(4))2017 2035, 2013.
Bruno A Olshausen and David J Field. Sparse coding with an overcomplete basis set: A strategy employed by v1? Vision research, 37(23):3311 3325, 1997.
Samet Oymak, M Amin Khajehnejad, and Babak Hassibi. Recovery threshold for optimal weight 11 minimization. In 2012 IEEE International Symposéum on Information Theory Proceedings, pp. 2032 2036.
IEEE, 2012.
Yagyensh Chandra Pati, Ramin Rezaiifar, and Perinkulam Sambamurthy Krishnaprasad. Orthogonal matching pursuit: Recursive function approximation with applications to wavelet decomposition. In Proceedings of 27th Asilomar conference on signals, systems and computers, pp. 40 44. IEEE, 1993.
Graeme Pope, Annina Bracher, and Christoph Studer. Probabilistic recovery guarantees for sparsely corrupted signals. IEEE transactions on information theory, 39(5) 3116, 2013.
Jason Tyler Rolfe and Yann LeCun. Discriminative recurrent sparse auto-encoders: 1st international conference learning representations, iclr 2013. In 1st International Conference Learning Representations, ICLR 2013, 2013.
Bo Shen, Rakesh R Kamath, Hahn Choo, and Zhenyu Kong. Robust tensor decomposition based back- ground/foreen fforeround separation in noisy videos and its applications in additive manufacturing IEEE Transactions on Automation Science and Engineering, 2022.
Dror Simon and Michael Elad. Rethinking the ese model for natural images. In Proc. Advances in Neural Information Processing Systems, pp. 2271-2281, 2019.
J-L Starck, Michael Flad, and David T, Donoho. Image decomposition via the combination of sparse representations and variational approach. IEEE transactions on image processing, 14(10):1570 1582, 2005.
Jean-Luc Starck, Michael Elad, and David L. Donoho. Redundant multiscale transforms and their application for morphological component separation. Advances in Imaging and Flectron Physics, 132:287-346, 2004.
Christoph Studer and Richard G Baraniuk. Stable restoration and separation of approximately sparse signals. Applied and Computational Harmonic Analysis, 37(1): 2014.
Christoph Studer, Patrick Kuppinger, Graeme Pope, and Helmut Boleskei. Recovery of sparsely corrupted signals. IEFE. Transactions Information Theory, 58(5):3115-314 2011.
23

---

Published in Transactions on Machine Learning Research (8/2024)
J. Sulam, A. Aberdam, A. Beck, and M. Elad. On multi-layer basis pursuit, efficient algorithms and convolutional neural networks. IEEE Transactions Paltern Analysis and Machine Intelligence, pp. 1-1, 2019. ISSN 1939-3539. doi: 10.109//PPAML2211.2200
Andrei Nikolaevich Tikhonov, AV Goncharsky, VV Stepanov, and Anatoly Yagola. Numerical methods for the solution of ill-posed problems, volune 328. Springer Science Business Media, 1995.
B. Tolooshams, S. Dey, and D. Ba. Deep residual autocncoders for expectation maximization-ime insiiire
dictionary learning. IEEE Transactions on Neural Networks and Learning Systems, pp. 1 1-, 2020. doi: 200.
Joel A Tropp. Greed is good: Algorithmic results for sparse approximation. IEFE Transactions on Information theory, 50(10):2231 2242, 2004.
Joel A Tropp and Anna C Gilbert. Signal recovery from random measurements via orthogonal matching pursuit. IEEE Transactions on information theory, (3(12):463546666 2007.
Namrata Vaswani and Wei Lu. Modified-cs: Modifying compressive sensing for problems with partially known support. IEEE Transactions on Signal Processing, 58(9):4595-48 4607, 2010.
Luminita A Vese and Stanley J Osher. Modeling textures with total variation minimization and oscillating patterns in image processing. Journal of scientific computing, 19(1):553-555 572, 2003.
John Wright and Yi Ma. Dense error correction via. I1-minimization. IEEE Transactions on Information Theory, 56(7):3540 3560, 2010.
Hao Yan, Kamran Paynabar, and Jianjun Shi. Anomaly detection in images with smooth background via smooth-sparse decomposition. Technomelries, 59(1):102 114, 2017.
Javier Zazo, Bahareh Tolooshams, and Demba Ba. Convolutional dictionary learning in hierarchical networks. In Proc. 2019 IEFE 8th International Workshop on Computational Advances in Mulli-Sensor Adaplive Processing (CAMSAP), pp. 131 135. IEEE, 2019.
Xiaowei Zhou, Can Yang, and Weichuan Yu. Moving object detection by detecting contiguous outliers in the low-rank representation. IEEE transactions on pottern analysis and machine intelligence, 35(3):597 610, 2012.
A Classification and Image Denoising
We warm start the networks by training the autoencoder for 150 epochs using the ADAM optimizer where the weights are initialized with the random Gaussian distribution. Within the network, agy Qus and X are tuned follows: ag and a, are step sizes of the gradient-based iteration; hence, they are chosen to make sure that the recurrence is contractive while they are large enough to make sure gradient information is effective from one another to another. Similarly, A₂ is empirically chosen based on the training performance where lambda, is small enough (to result in non-zero representation), and large enough (to visually observe sparse feature maps). We note that a systematic grid search may improve upon the reported result; however, we suffice to the above-discussed approach as the goal of our paper is a comparative study in a similar training/tuming situation.
The learning rate is set to 10-3, 3, We set of the optimizer to be 10 15 and used batch size of 16. For disjoint classification training, we trained for 1,000 epochs, and for joint classification training, the network is trained for 500 epochs. All the networks use FISTA (Beck & Teboulle 2009) within their encoder for faster sparse coding. Table 5 lists the parameters of the different networks. Figure g visualizes the most important atoms for reconstruction and classification for disjoint training.
Figure 10 visualizes the reconstruction of MNIST test image for the disjoint training, where the autoencoder is trained for pure reconstruction (8 0).
24

---

Published in Transactions on Machine Learning Research (8/2024)
Table 5: Network parameters for MNIST classification experiment.
DenSaE CSCNethyp
CSCNetts
# dictionary atoms
400
Image size
28 x8
# training examples
50,000 MNIST
# validation examples
10,000 MNIST
# testing examples
10,000 MNIST
# Irainable paramelers in the auloencoder
313,600
313,600
314,000
# trainable parameters in the classifier
4,010
4,010
4,010
S(.)
ReLU
Encoder layers T
15
0g
0.02
Or
0.02
Xinit
0.5
0.5
0.0
A rec.
A rec.
A rec.
B rec.
B rec.
B rec.
B rec.
B rec.
class
class
B class
B class
B class
(a) SCNelys
(b) SCNeltyp
(d)
DenSaE (e)
DenSaF
(c) DenSaF 5A395B 25A375B
200
Figure 9: Most important atoms of the dictionary used for reconstruction (rec.) and classification (class.) for disjoint training.
The figure shows that SCNetts has the best reconstruction among all, and the second best is DenSaE having the highest number of A atoms. Figures 11 visualizes the reconstruction of MNIST test. image for the joint training when 3 = 1. Notably, in this case, the reconstructions from SCNet do not look like the original image. On the other hand, DenSaE even with 3 = 1 is able to reconstruct the image very well. In addition, the figures show how Ax and Bu are contribution for reconstruction for DenSaE.
We note that as our network non-convolutionall we do not compare to the stato-of-tho-art, a convolutional network. We do not compare our results with the network in Rolle & LeCun (0133) that work does not. report reconstruction loss and it involves sparsity enforcing loss that change the learning behaviour.
For dcnoising, all the trained networks implement FISTA for faster sparse coding. Table D lists the parameters of the different worksr.s Moreover, Figure 12 shows the histogram of learned biases by CSCNetrs for various noise levels. We note that compared to CSCNet, which has 63K trainable parameters, all the trained networks including CS have 20x fewer trainable parameters. We attribute the difference performance, compared the results reported in the CSCNet paper, this large difference in the number of trainable parameters and the usage of larger dataset.
25

---

Published in Transactions on Machine Learning Research (8/2024)
y
2
3
4 5
6
7 8
2
3
4
5 6
7
8
1 2
3
4
5
6
7
8
9
0
1 2 3 4 5 6
9
0
/
2
3 4 5 6
9
0
2
3
4
5
6
(a) Original Ax
(b) SCNelrs
(c)
SCNelhyp Ax
Ax
00000000
S00000 00000000 20100
1 2
3
4
5
6
7
8
9 0
2
3
4
5
6
Bu
Bu
Bu
2
3
5
6 7
8
2 3 9 0
3 /
4
6
7
8 6
2
3
4
5
6
7
8 6
9
0
/
2
3
4
5
6
2
3
4
5
9 0
2
3
5
y
2
3
4
5
6
7 8
2
3
4
5
6
7 8
1 2 3
4
5
6
7
8 6
9
0
/
2
3
4
5 6
9
0
2
3
4
5
6
9
0
2
3
4
5
(d) DenSaE 5A 3955B
(e) DenSaE 3753
(f) DenSaE 200 A 200B
Figure 10: Reconstruction of MNIST test. images for disjoint classification.
y
2
3
4 5 6 7 8
1
2
3
4 2
5
8 6
9
0 / 2 3 4 5 6
9
3
4
(a)
Original Ax
(b) SCNetts
(c) SCNetuyp
Ax
Ax
Bu
Bu
Bu
2
3
5
6
7 8
3
4
6
7
1
2
3
4
5
8
9
0
1
2
3
4
5 6
9 O
1
2
3
4
5
9
0
2
3
4
5
4
ý
ý
f
2
3
4
5
6
7
8
2
3
4
5
6
7 8
1 2 3
4
5
6
8 4
9
0
2
3
4
5
6
9
2
3
4
5
6
9
4
2
3
5
(d) DenSaF 5A395B
(e) DenSaE A55B
( DenSaE 200B
Figure 11: Reconstruction of MNIST test images for joint classification when f
26

---

Published in Transactions on Machine Learning Research (8/2024)
8
8
Count
Count
6
6
4
4
2
2
0
0
-3
-2.5
-2
-15
-0.8
-3
-2.5
-1.5
-0.8
Filter biases (log scale)
Filter biases (log scale)
(a) 7 15
(b) r 25
10
10
8
8
Count
Count
6
6
4
4
2
2
0
0
-3
-2.5
-2
-15
-0.8
-3
-2.5
-2
-1.5
-0.8
Filter biases (log scale)
Filter biases (log scale)
(c) 50
(d) 75
Figure 12: Histogram of biases from CSCNet1s for various noise levels.
Table Network parameters for natural image denoising experiments.
DenSaE
CSCNethyp
CSCNetLs
# filters
64
Filter size
7x7
Strides
5
Patch size
128 x 128
# training examples
432
BSD432
#
lesting examples
68 BSD68
#
trainable parameters
3,136
3,136
3,200
S(.)
Shrinkage
Encoder layers T
15
On
0.1
Or
0.1
7 15
0.085
0.085
0.1
T 25
0.16
0.16
0.1
init
т 50
0.36
0.36
0.1
75
0.56
0.56
0.1
B Euclidean norm distribution
61-
Figure 13: Euclidean norm distribution for the components Ax and Bu MNIST images.


Reviews:
[{"review_id": "eTYSDb5f5R", "reviewer": "Reviewer_R52K", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n- The writing style is clear and calm. The authors take great care and time to introduce the context and related works.\n- The theoretical results are interesting, the overlay of dense and sparse features is natural and it is interesting to see how this case comparse to the separate cases.\n- The empirical results compare the performance of two different architectures of autoencoders, informed by different principles, in depth. Notably they go beyond this by introspecting the models and giving intuitive explanations for the different/similar performances.\n\n### Weaknesses\n- The empirical evaluation is not comprehensive in terms of the variety of real-world data explored.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work examines a signal recovery where given a measurement y the goal is to recover a sparse vector u and a dense vector x as sensed through two separate matrices.\nThe authors provide criteria on the matrix and signal under which given vectors u and v are unique solutions under the optimization problem and provide an algorithm to recover them via convex optimization. \nIn their experiments, they show the phase transitions for perfect recovery in terms of the ratios of sparsity, number of measurements and the dimension of the original vectors.\nThey compare how their novel autoencoder architecture, which is informed by their previous analysis to simultaneously optimize a sparse and a dense representation, compares to only sparse approaches in the case of MNIST images.\nWhile their model is better in many case, they reveal an interesting connection between the two models and show that the sparse model implicitly follows a similar approach as the dense model.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "### Up to the authors\nThe empirical analysis would be nicely complemented by a supplementary analysis of a dataset that exhibits different levels of supposed sparsity than BDS68. It would be also nice to understand that (e.g. more sparse) types of noise or corruption influence the learned dictionaries in a predicable way.\n\n### Form - should definitely be incorporated\n- all over the manuscript \\citep and \\cite were not used appropriately\n- Sec.2.2, first sentence, is -> in\n- Sec.2.2., fat is not clear from context\n- Sec.2.3., first sentence, do you mean u instead of y?\n- End Proof Thm 4 -> follows\n- Fig.1 label color bar\n- Sec.5.3. \"In order to further validate ...\" -> one 'the' too many\n- Sec.5.3. sprase -> sparse\n- (27)-(29) define the size of X, U, what is the range of l?\n- (27) why do the matrices do not have a l-index?\n- Sec.5.4. (i) filters is used the first time -- what exactly is meant?\n- Sec 5.3. last sentence -> missing a \"the\"\n- Sec 5.4.2 (see ??? 10)", "broader_impact_concerns": "I have no concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "CGHkk6N8td", "reviewer": "Reviewer_SLyA", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths** \n\nOverall, the paper is well written and easy to follow.\n\nThe authors present a new sparse coding problem that uses two types of dictionaries and learns sparse and dense components.\n\nThey provide theoretical analysis and describe conditions for unique solutions.\n\nSynthetic data is used to validate that the solution can be recovered with high probability. \n\n**Weaknesses**\n\nThe motivation for the proposed model is not really clear. I do understand the importance of sparse coding and its multiple use cases in denoising images and audio signals. However, I do not fully understand what advantages are gained from the proposed setting. Specifically, in what cases is it important to balance between representation and discriminative power? \n\nOn the same note, the applications are semi-synthetic. What real-world problem should the reader be using this model for?\n\nOverall, the proposed model's performance on real data seems comparable to the existing SCNet, and the authors have not highlighted which data regime their method is beneficial for and vice versa.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors focus on the problem of sparse coding and propose a new model for learning to represent a vector $y$ using a sparse representation $u$ based on two dictionaries, $A$ and $B$. The key idea is that $A$ captures low-frequency components of the signal, while $B$ captures high-frequency components. The authors argue that this approach allows for a balance between the model's discriminative and representation power. The authors demonstrate the feasibility of their solution for the proposed sparse coding problem, showing that by using convex optimization, they can recover $x$ and $u$. Finally, they use unrolling to present a dense and sparse autoencoder that demonstrates good representation and discriminative capabilities on the MNIST dataset.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Have you considered adding a balancing term between the first and second terms in Eq. 1? \n\nSection 2.1 can you add intuition about applications of compressive sensing from a union of dictionaries? This would help the reader understand the motivation behind this work. Also, in the introduction, it would be useful to present some possible applications for the dense and sparse coding problem.\n\nSection 3: “our the” one of these words should be removed\n\nSection 3.2: Theorem 1 Candes &.. There are two brackets; remove one\nPlease describe $\\beta$ after its first appearance. For example: where $\\beta$ is some constant.. \n\nCommas missing after equations 5 and 8.\n\n\nSection 5.1 \\sigma is introduced with respect to m,n,p, but those are only mentioned later. This is confusing; please try to improve the presentation of this part to enhance clarity.\n \nCVXY is never introduced.\n\nThe last paragraph of section 5.1 writing has some repetition of words such as model and explicitly.\n\nPhase transition is described but please explain that the plot represents the probability of successful recovery (this is not explained).\n\nFigure 2 x-axis overlaps with subfigure names.\n\nFigure 3, the differences are very subtle it is hard to understand the usefulness of the method from this example. Typically, a synthetic example with visualizations should convey the main message of the method clearly.\n\nSection 5.3 third paragraph: “the both the”\n\nFigure 4 shows some differences between Bu and Ax, but again this seems relatively subtle. \n\nSection 5.4 “the parameters .. are tuned via a grid search”. With how many values, what range, and with what objective?\n\nP15. After the questions, the citations for Simon & Elad should be in brackets.\n\nLast paragraph of P15 why are you using << for 32.61 and 47.7 and < for 32.61 and 71.3\n\nP16 What are the train test splits for these experiments? Are they performed several times?\n\nOn the same page what is $\\beta$ please refer to the place it is described.\n\nTable 4 without standard deviations, it is hard to compare these results; both DenSaE and CSCNet_{ls} seem to obtain similar results.", "broader_impact_concerns": "No concerns", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "6hN9XY0Crt", "reviewer": "Reviewer_jK8w", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is clearly written, well-organized, and sufficiently reviews prior works.\n\nThe experiments are solid and the theoretical results are interesting.\n\nA major weakness is that the theorems seem simple to prove; they are based on basic linear algebraic techniques.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper tackles the problem of reconstructing two signals, one dense and one sparse, by minimizing a quadratic term for the dense signal and a $\\ell_1$ term for the sparse signal, subject to linear constraints.\n\nTheoretical results are proved, which give conditions under which the unique recovery of both signals is possible.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "It is important to compare with the naive idea where one writes $y=Ax+bu = [A, B] [x, u]^\\top$. In this case, we are given the data matrix $C=[A, B]$ and we know our variable $v:=[x, u ]^\\top\\in \\mathbb{R}^{p+n}$ is $p+k$ sparse. With this, we can apply existing results and obtain conditions that guarantee unique recovery. How do the proposed conditions compare with this approach? Are the proposed conditions better? Such a comparison needs to be included in the revision.", "broader_impact_concerns": "Broader impact concerns do not apply to the present manuscript.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Please consider improving your experimental section according to the reviewers' comments.
Decision: Accept (poster)