Early-type dwarf galaxies, once believed to be simple systems, have recently been shown to exhibit an intriguing diversity in structure and stellar content. To analyze this further, we started the SMAKCED project (Stellar content, MAss and Kinematics of Cluster Early-type Dwarfs, http://www.smakced.net) and obtained deep H-band images for 101 early-type dwarf galaxies in the Virgo Cluster in a brightness range of -19 mag <= Mr <= -16 mag, typically reaching a signal-to-noise ratio of 1 per pixel of ~0farcs25 at surface brightnesses ~22.5 mag arcsec-2 in the H band. Here we present the first results of decomposing their two-dimensional light distributions. This is the first study dedicated to early-type dwarf galaxies using the two-dimensional multi-component decomposition approach, which has been proven to be important for giant galaxies. Armed with this new technique, we find more structural components than previous studies: only a quarter of the galaxies fall into the simplest group, namely, those represented by a single Sérsic function, optionally with a nucleus. Furthermore, we find a bar fraction of 18%. We also detect a similar fraction of lenses which appear as shallow structures with sharp outer edges. Galaxies with bars and lenses are found to be more concentrated toward the Virgo galaxy center than the other sample galaxies.