I What is the difference between a complete basis and an overcomplete dictionary?

  • I
  • Thread starter Thread starter fog37
  • Start date Start date
  • Tags Tags
    Bases
fog37
Messages
1,566
Reaction score
108
TL;DR Summary
Dictionary Learning and Bases
Hello Forum,

I am trying to get a grasp of the topic (new to me) of dictionary and dictionary learning. In general, we express a vector ##A## using a basis.
A basis is a complete set of vectors that we can use to expand any other vector as a linear combination of the basis vectors. For example, a signal ##x(t)## can be expanded in the Fourier basis, in the Dirac delta basis, etc. These are examples of orthogonal bases (any pair of the basis vectors are uncorrelated with each other). The same signal can also be expanded using wavelets (wavelet transform) or cosines (cosine transform), etc.

Now on to dictionaries: a dictionary is an overcomplete set of vectors. We can use the dictionary atoms to write an arbitrary vector as a weighted sum of the atoms. In general, we always seek bases because we can get the expansion coefficients via inner products.

What is the point of a dictionary where some of the vectors are correlated and the set is overcomplete?
Does the inner product still provides the coefficients?

Say we have vector ##A## in ##R2##. All the possible bases will have exactly two basis vectors. We use the basis ##B= (B1, B2)##. We can write $$A= b1 B1 + b2 B2$$
Say we have a dictionary ##D= (d1,d2,d3,d4)## which can also be used to express $$A= d1 D1 + d2 D2+ d3 D3+d4 D4$$

Is that correct?

What is dictionary "learning" then?
 
Physics news on Phys.org
fog37 said:
Say we have a dictionary ##D= (d1,d2,d3,d4)## which can also be used to express $$A= d1 D1 + d2 D2+ d3 D3+d4 D4$$

Is that correct?
Yes, although for an overcomplete dictionary (where the number of atoms is greater than the number of dimensions) we are usually interested in sparse (not necessarily exact) representations where (using your notation) the number of non-zero ## d_k ## values that represent each ## A ## is less than the number of dimensions.

fog37 said:
What is dictionary "learning" then?
Creating a dictionary that for a given number of atoms optimizes the sparsity and the accuracy of the representations.
 
Last edited:
fog37 said:
Summary:: Dictionary Learning and Bases

Hello Forum,

I am trying to get a grasp of the topic (new to me) of dictionary and dictionary learning. In general, we express a vector ##A## using a basis.
A basis is a complete set of vectors that we can use to expand any other vector as a linear combination of the basis vectors. For example, a signal ##x(t)## can be expanded in the Fourier basis, in the Dirac delta basis, etc. These are examples of orthogonal bases (any pair of the basis vectors are uncorrelated with each other). The same signal can also be expanded using wavelets (wavelet transform) or cosines (cosine transform), etc.

Now on to dictionaries: a dictionary is an overcomplete set of vectors. We can use the dictionary atoms to write an arbitrary vector as a weighted sum of the atoms. In general, we always seek bases because we can get the expansion coefficients via inner products.

What is the point of a dictionary where some of the vectors are correlated and the set is overcomplete?
Does the inner product still provides the coefficients?

Say we have vector ##A## in ##R2##. All the possible bases will have exactly two basis vectors. We use the basis ##B= (B1, B2)##. We can write $$A= b1 B1 + b2 B2$$
Say we have a dictionary ##D= (d1,d2,d3,d4)## which can also be used to express $$A= d1 D1 + d2 D2+ d3 D3+d4 D4$$

Is that correct?

What is dictionary "learning" then?
Re Fourier series, you may want to consider that they use infinite bases and you're dealing with convergence issues, rather than equality here (i.e., a Schauder basis, rather than your Hamel basis in finite dimension).
 
Hello again,
I found this at resource on frame and dictionaries at https://www.egr.msu.edu/~aviyente/ece802lecture9.pdf

1651705420128.png


In what sense are larger dictionary (overcomplete set of building vectors called atoms) more suitable for representing in a sparse way signals that have lots of structure?

Could anybody providing some clarifications? I am stuck with the idea of a complete basis as the best choice to represent an arbitrary signal...

Representing a signal using a frame, instead of a basis, leads us to several possible linear representations of the same signal which does not have a single unique representation. Apparently this is useful to create a simpler, more sparse representation of a signal...but why?
 
You are confusing the two parts of the notes you linked. The first part is about frames and ends with the summary on slide 9:
  • Frames are an overcomplete version of a basis set, and tight frames are an overcomplete version of an orthogonal basis set.
  • The frames and tight frames have a certain amount of redundancy. In some cases, redundancy is desirable giving a robustness to the representation. In other cases, redundancy is an inefficiency.
  • In finite dimensions, vectors can be removed from a frame to get a bases, but in infinite dimensions, that is not possible.

The second part starts with the slide you quoted and is about overcomplete dictionaries: these are not the same thing as frames.

A simple example of an overcomplete dictionary is a postal code: I am going to use the UK postcode system. We can represent the location of 10 Downing Street in eight characters using its postcode SW1A 2AA. This is more compact than using the orthoganal basis of latitude and longitude 51.5033N0.1277W.
 
pbuk said:
You are confusing the two parts of the notes you linked. The first part is about frames and ends with the summary on slide 9:The second part starts with the slide you quoted and is about overcomplete dictionaries: these are not the same thing as frames.

A simple example of an overcomplete dictionary is a postal code: I am going to use the UK postcode system. We can represent the location of 10 Downing Street in eight characters using its postcode SW1A 2AA. This is more compact than using the orthoganal basis of latitude and longitude 51.5033N0.1277W.
Thank you pbuk! I really like your postcode example. Just checking my understanding, hopefully useful for other beginners like me who don't fully appreciate the power of frame and dictionaries...
  • From what I understand, a frame is like the generalized version of a basis. A basis, a particular type of frame, is a complete set of independent vectors. Not all frames are bases but all bases are frames. A frame is generally a complete set of dependent vectors (essentially a non-orthogonal basis).
  • "Complete" means that the basis or frame has as many basis/frame vectors as the dimension of the space a vector lives in: if our vector ##X## lives in ##R3##, then any complete frame or basis would have 3 building block vectors.
  • Using an analogy, frames are like the letters of an alphabet (and there are many alphabets).
  • When we use complete but non-orthogonal bases, a hypothetical vector ##X## does still has a unique representation (linear superposition of the non orthogonal basis vectors) as it happens when we use bases but the coefficients cannot be easily calculated via dot products.
  • My understanding is that "dictionary" and "frame" are synonyms.
  • An overcomplete dictionary seems to be a frame with a number of dependent vectors that is larger than the dimensionality of the vectors we are interested in representing. Using an overcomplete dictionary, a vector ##X## does NOT have a unique representation but multiple valid representations (redundancy). Also, we don't have to use all the atoms in the dictionary to represent the vector (something we need to do when we use a basis).
The interesting part (at least for me), is that certain types of vectors can have a sparser representation in an overcomplete dictionary than in a complete basis or frame. For example, let's consider 2 different alphabets.
Alphabet 1 has 5 letters and is an overcomplete dictionary with the following atoms $,@,%,&,*
Alphabet 2 has letters and is a complete basis with the atoms/letters O,U,W.

We could write the same word using either alphabet but we would, somehow, get both a redundant (i.e. multiple linear expansions are possible) and sparser representation using alphabet 1 even if alphabet 2 is shorter. That is cool.

Thank you!
 
I asked online questions about Proposition 2.1.1: The answer I got is the following: I have some questions about the answer I got. When the person answering says: ##1.## Is the map ##\mathfrak{q}\mapsto \mathfrak{q} A _\mathfrak{p}## from ##A\setminus \mathfrak{p}\to A_\mathfrak{p}##? But I don't understand what the author meant for the rest of the sentence in mathematical notation: ##2.## In the next statement where the author says: How is ##A\to...
The following are taken from the two sources, 1) from this online page and the book An Introduction to Module Theory by: Ibrahim Assem, Flavio U. Coelho. In the Abelian Categories chapter in the module theory text on page 157, right after presenting IV.2.21 Definition, the authors states "Image and coimage may or may not exist, but if they do, then they are unique up to isomorphism (because so are kernels and cokernels). Also in the reference url page above, the authors present two...
When decomposing a representation ##\rho## of a finite group ##G## into irreducible representations, we can find the number of times the representation contains a particular irrep ##\rho_0## through the character inner product $$ \langle \chi, \chi_0\rangle = \frac{1}{|G|} \sum_{g\in G} \chi(g) \chi_0(g)^*$$ where ##\chi## and ##\chi_0## are the characters of ##\rho## and ##\rho_0##, respectively. Since all group elements in the same conjugacy class have the same characters, this may be...

Similar threads

Back
Top