What is the method in dictionary learning that does not have an overcomplete dictionary? And what is the difference in minimization between these two methods (one using overcomplete dictionary and another using the smaller dictionary)?
First of all I am curious about your use-case because I think you might be looking at the wrong tool for the job. Dictionary learning is useful when dealing with sparse representations. The idea of an overcomplete dictionary is that you have many bases from which to choose a few columns to represent a given signal.
To put it another way, if a signal is using most of the vectors from a fixed base (like Fourier, Wavelet, DCT) it might be because that base is missing some key features of that signal (e.g. not all signals can be expressed properly as sines). So if you have multiple bases there's a better chance of finding far fewer vectors from different bases to represent the same thing resulting in a sparse representation.
The fewer vectors (atoms) in your dictionary, the less chances to get a proper sparse representation. So usually there is no point in learning a square block.
There is an exception to this where multiple orthonormal blocks are learned and their union is used as the overcomplete dictionary, look-up SBO and UONB. The algorithm that learns a single base (block) is called 1ONB.