Sorting with self-organizing maps

Area of Science:

• Computational Neuroscience
• Machine Learning
• Algorithm Analysis

Background:

• Self-organizing feature maps (SOFMs) are unsupervised neural networks.
• SOFMs are known for their ability to perform dimensionality reduction and clustering.
• Their computational complexity for sorting tasks has not been fully explored.

Purpose of the Study:

• To analyze the time complexity of sorting real numbers using a self-organizing feature map.
• To investigate the conditions under which SOFMs achieve linear time sorting.
• To identify potential performance limitations and pathological cases.

Main Methods:

• Theoretical analysis of the self-organizing feature map algorithm.
• Examination of sorting time complexity based on input data distribution.
• Identification of worst-case scenarios for sorting performance.

Main Results:

• Self-organizing feature maps can sort n real numbers in O(n) time under uniform data distribution.
• This linear time performance appears to violate the theoretical O(n log n) sorting bound.
• Pathological data distributions can result in O(n^2) sorting time, though these are exponentially rare.

Conclusions:

• The learning process in SOFMs can result in efficient, emergent sorting algorithms.
• Performance is highly dependent on input data distribution.
• SOFMs offer a unique approach to sorting with potential advantages in specific data scenarios.