AI-enabled precision medicine promises a transformational improvement in healthcare outcomes, however training on biomedical data presents a challenge: it is often high dimensional and clustered, with limited observations. To overcome this, we propose a simple and scalable approach for cluster-aware embedding that combines embedding methods with a convex clustering penalty. Our approach outperforms fourteen clustering methods on highly underdetermined problems (e.g., limited observations) as well as on large sample datasets, and yields interpretable embedding dendrograms. Thus our novel approach improves significantly on existing methods, and enables finding scalable and interpretable biomarkers for precision medicine.