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, and obtained deep H-band images for 101 early-type dwarf galaxies in the Virgo cluster in a brightness range of -19 leq M_r leq -16 mag, typically reaching a signal-to-noise of 1 per pixel of sim0.25 at surface brightnesses sim22.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 Sersic function, optionally with a nucleus. Furthermore, we find a bar fraction of 18%. We detect also 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 towards the Virgo galaxy center than the other sample galaxies.